POJ 2480 Longge's problem 積性函數(shù)
來源：程序員人生 發(fā)布時(shí)間：2014-09-11 10:09:04 閱讀次數(shù)：2894次
題目來源：POJ 2480 Longge's problem
題意：求i從1到n的gcd(n, i)的和
思路：首先如果m, n 互質(zhì) gcd(i, n*m) = gcd(i, n)*gcd(i, m) 這是一個(gè)積性函數(shù)積性函數(shù)的和還是積性函數(shù)
由歐拉函數(shù)知識(shí)得 phi(p^a) = p^a - p^(a-1) p是素?cái)?shù) a是正整數(shù)
得到最終答案f(n) = f(p1^a1)*f(p2^a2)*...*f(pn^an) 其中f(p^a) = a*(p^a-p^(a-1))+p^a
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
//篩素?cái)?shù)
int vis[maxn];
LL prime[maxn];
LL pow_mod(LL a, LL p)
{
LL ans = 1;
while(p)
{
if(p&1)
{
ans *= a;
}
a *= a;
p >>= 1;
}
return ans;
}
void sieve(int n)
{
int m = sqrt(n+0.5);
memset(vis, 0, sizeof(vis));
vis[0] = vis[1] = 1;
for(int i = 2; i <= m; i++)
if(!vis[i])
for(int j = i*i; j <= n; j += i)
vis[j] = 1;
}
int get_primes(int n)
{
sieve(n);
int c = 0;
for(int i = 2; i <= n; i++)
if(!vis[i])
prime[c++] = i;
return c;
}
int main()
{
int c = get_primes(200000);
int cas = 1;
int T;
LL n, ans;
while(scanf("%I64d", &n) != EOF)
{
ans = 1;
for(int i = 0; i < c && prime[i]*prime[i] <= n; i++)
{
if(n%prime[i] == 0)
{
LL sum = 0;
while(n%prime[i] == 0)
{
sum++;
n /= prime[i];
}
ans *= sum*(pow_mod(prime[i], sum)-pow_mod(prime[i], sum-1))+pow_mod(prime[i], sum);
}
}
if(n > 1)
{
ans *= n-1+n;
}
printf("%I64d
", ans);
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
