#include <stdio.h>
#define maxf 30
unsigned int N,mexp[maxf],top,base[maxf],expt[maxf];
long long cnt;

void factorDecomp(int n)
{
    int i=2;top=0;
    for(;i*i<=n;i++) if(n%i==0){
        base[top]=i;
        expt[top]=0;
        while(!(n%i))
        {
            n/=i;
            expt[top]++;
        }
        top++;
    }
    
    if(n>1){
        base[top]=n;
        expt[top]=1;
        top++;
    }
}

void dfs(int m,int d, int ev){
    int v=1,e=1;if(d==top) {
        int g=N/m;
        cnt+=g*ev;
        return ;
    }
    dfs(m,d+1,ev);
    for(;v<=expt[d];v++,e*=base[d]) {
        mexp[d]=v;
        dfs(m*base[d]*e, d+1, ev*(base[d]-1)*e);
    }
}

int main()
{
    while(scanf("%u",&N)==1){
    //while(cin>>N) {
        factorDecomp(N);
        cnt=0;
        dfs(1,0,1);
        printf("%I64d\n",cnt);
        //cout<<cnt<<endl;
    }
    return 0;
}

• 为什么这份代码31ms过了？差距在哪个地方? (956) qiqilrq 2007-08-03 02:08:38