poj2480 Longge's problem ——积性函数入门题

April 21, 2013
POJ Math

题目链接：http://poj.org/problem?id=2480 题目大意：　　给定一个数字N，求∑gcd(i, N) 1<=i <=N 的值。题目思路：　　x是一个数字，m与n互素，则gcd(x,m*n) = gcd(x, m) * gcd(x, n) 令g(y) = gcd(x, y) 那么g(y)是一个积性函数。令f(N) = ∑gcd(i, N) 　　满足gcd(x, n) = 1 的个数是欧拉函数φ(n)，那么可以知道，满足gcd(x, n) = p 的个数可以这么求：x 和 n 同时除以 p ，那么gcd(x/p, n/p) = 1 ，那么个数就是φ(n/p)。　　分解N = p1^a1 * p2^a2 * …… *pn^an ，则f(N) = f(p1^a1 * p2^a2 * …… *pn^an) = f(p1^a1) * f(p2^a2) * …… * f(pn^an)；　　可以枚举pi^ai的因数，对于f(pi^ai) = 1 * φ(pi^ai) + pi * φ(pi^(ai-1)) + pi^2 * φ(pi^(ai-2)) + …… + pi^(ai-1) * φ(pi) + pi^ai * φ(1)；　　根据φ(pi^ai) = pi^ai - pi^(ai-1)，那么可以化简上面的式子：f(pi^ai) = ai * pi^ai + ai * pi^(ai-1) + pi^ai = pi^ai * (ai + ai/pi + 1)；　　所以，f(N) = N * (a1 + a1/p1 + 1) * (a2 + a2/p2 + 1) * …… * (an + an/pn + 1)。　　这题当然不是自己想出来的，但是学习了一下积性函数，看的神牛的解题代码：http://hi.baidu.com/lydrainbowcat/item/66a0c9088f876f12acdc70ba 说来这神牛是我的学弟，比我小一届貌似，一个高中的，竟然还都是省理的，唉……惭愧　　不说了，都是泪……什么也不想了，专注刷题。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
LL n, i, j, ans;
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj2480.in", "r", stdin);
#endif
  while (~scanf("%lld", &n)){
    ans = n;
    for (i = 2; i * i <= n; ++i){
      j = 0;
      if (n % i == 0){
        while (n % i == 0){
          j++; n /= i;
        }
        ans /= i; ans = ans * (i * j - j + i);
      }
    }
    if (n > 1){
      ans /= n; ans = ans * (n - 1 + n);
    }
    printf("%lld\n", ans);
  }

  return 0;
}

　　开始用cin,cout超时一次，后来发现 i ，j，不应该用 int ，应该用LL，这才过了，32ms 　　另外一份比较快的代码：谢谢Wahaha_hnu llw学长，还没看懂，继续有时间继续研究


#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

typedef __int64 LL;
#define N 70000

LL n;
LL f[N],prime[N],primeNum;
LL a[N],b[N],cnt, ans;
bool vis[N];
void sieve()
{
    int i,j;
    for(i=0;i<N;i++) f[i]=1;
    f[0]=f[1]=0;
    for(i=2;i*i<N;i++)
        if(f[i])
            for(j=i*i;j<N;j+=i)
                f[j]=0;
    j=0;
    for(i=2;i<N;i++)
        if(f[i])
            prime[j++]=i;
    primeNum=j;
}
void dfs(int k,LL x)
{
    int i,j;
    LL y,t;
    if(k==cnt)
    {
        y=n/x;
        for(i=0;i<cnt;i++)
            if(!vis[i])
                y-=y/a[i];
        ans+=x*y;
//        printf("x=%I64d y=%I64d\n",x,y);
        return ;
    }
    t=1;
    for(i=0;i<b[k];i++)
    {
        dfs(k+1, x*t);
        t*=a[k];
    }
    vis[k]=1;
    dfs(k+1, x*t);
    vis[k]=0;
}
int main()
{
    int i,j,k;

    sieve();
    while(scanf("%I64d",&n)==1)
    {
        LL x=n;
        cnt=0;
        for(i=0;i<primeNum &&prime[i]*prime[i]<=x;i++)
            if(x%prime[i]==0)
            {
                a[cnt]=prime[i], b[cnt]=0;
                while(x%prime[i]==0)
                    b[cnt]++, x/=prime[i];
                cnt++;
            }
        if(x>1) a[cnt]=x, b[cnt]=1, cnt++;
//        printf("cnt=%I64d\n",cnt);
//        for(i=0;i<cnt;i++)
//            printf("%I64d %I64d\n",a[i], b[i]);

        ans=0;
        memset(vis,0,sizeof(vis));
        dfs(0,1);
        printf("%I64d\n",ans);
    }
  return 0;
}

　　这份代码可以16ms过的……

Read more