Divisors 欧拉函数的运用

Divisors 欧拉函数的应用

#include <stdio.h>
#include <cstring>
#define mm 500
bool fuck[mm];
int wokao[mm][100];
long long ca[mm][mm];
int p[100];
int main()
{
    int t=0,x,n;
    memset(fuck,0,sizeof(fuck));
    fuck[0]=fuck[1]=0;
    for(int i=2; i<=mm; i++)
    {
        if(!fuck[i]) p[t++]=i;
        for(int j=0; j<t&&i*p[j]<mm; j++)
        {
            fuck[i*p[j]]=true;
            if(!(i%p[j])) break;
        }
    }
    memset(wokao,0,sizeof(wokao));
    for(int i=0; i<t; i++)
        for(int j=2; j<mm; j++)
            wokao[j][i]=j/p[i]+wokao[j/p[i]][i];
    for(int i=2; i<mm; i++)
        for(int j=1; j<i; j++)
        {
            ca[i][j]=1;
            for(int k=0; k<t&&wokao[i][k]; k++)
            {
                int a=wokao[i][k]-wokao[j][k]-wokao[i-j][k];
                if(a)
                {
                    ca[i][j]*=(a+1);
                }
            }
        }
    while(scanf("%d%d",&n,&x)==2)
    {
        if(x==0||x==n)
        {
            printf("1\n");
            continue;
        }
        printf("%lld\n",ca[n][x]);
    }
    return 0;
}