AcWing 871. 约数之和
原题链接
简单
作者:
呼和
,
2019-10-16 19:55:59
,
所有人可见
,
阅读 599
不一样的题解
/*****************************************
Problem Name :
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 45000;
const int M = 20000;
const int Mod = 1e9 + 7;
int prim[N+M];
bool st[N+M];
int num[N+M];
int sum = 0;
int n;
void calc()
{
for(int i = 2; i < N ; i++)
{
if(!st[i])
prim[sum++] = i;
for(int j = 0 ; prim[j] * i <= N ; j++)
{
st[prim[j] * i] = true;
if(i % prim[j] == 0)
break;
}
}
}
int main()
{
calc();
cin >> n;
for(int i = 0,x ; i < n ; i++)
{
cin >> x;
for(int j= 0 ; x!= 1 && j < sum && prim[j] <= x ; j++)
{
while( x != 1 && x % prim[j] == 0)
{
num[j]++;
x /= prim[j];
}
}
if(x != 1)
{
prim[sum] = x;
num[sum++] = 1;
}
}
LL ans = 1;
for(int i = 0 ; i < sum ; i++)
{
if(num[i] != 0)
{
LL s = 1 + prim[i];
LL k = prim[i];
for(int j = 2 ; j <= num[i] ; j++)
{
k *= prim[i];
k %= Mod;
s += k;
s %= Mod;
}
ans *= s;
ans %= Mod;
}
}
cout << ans << endl;
}
hack:
3
1271401
318979
637958