Divisors 欧拉函数的应用
#include <stdio.h>#include <cstring>#define mm 500bool 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;}
