AcWing 870. 《算法基础课》约数--约数个数与约数之和
原题链接
简单
作者:
藕丝泥霸
,
2024-01-19 23:15:52
,
所有人可见
,
阅读 57
约数个数与约数之和
- 公式不列举了,这里贴两个具体的例子方便对公式理解:
- 约数个数知多少
- 一个整数的约数个数与约数之和的计算方法
代码
约数个数
#include<iostream>
#include<cstdio>
#include<unordered_map>
using namespace std;
typedef long long LL;
LL mod=1e9+7;
unordered_map<int,int> ha;
void calc(int x){
for(int i=2;i<=x/i;i++){
int cnt=0;
if(x%i==0){
while(x%i==0){
x=x/i;
cnt+=1;
}
ha[i]+=cnt;
}
}
if(x>1) ha[x]+=1;
}
int main(){
int n;
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x);
calc(x);
}
LL res=1;
for(auto r:ha){
res=res*(r.second+1)%mod;
}
printf("%lld\n",res%mod);
return 0;
}
约数之和
#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<cmath>
using namespace std;
typedef long long LL;
LL mod=1e9+7;
unordered_map<int,int> ha;
void calc(int x){
for(int i=2;i<=x/i;i++){
int cnt=0;
if(x%i==0){
while(x%i==0){
x=x/i;
cnt+=1;
}
ha[i]+=cnt;
}
}
if(x>1) ha[x]+=1;
}
int main(){
int n;
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x);
calc(x);
}
LL res=1;
for(auto r:ha){
int prime=r.first,cnt=r.second;
LL temp=1;
while(cnt--) temp=(temp*prime+1)%mod;
res=res*temp%mod;
}
printf("%lld\n",res%mod);
return 0;
}