这是我从codeforce中找到的一道题:
就是模拟,要注意边计算边取mod,这样才不会爆int~~
#include<stdio.h> int n; int judge(int num){ int tmp=1,i; for(i=1;i<=n-2;i++){ tmp=tmp*num%n; //边乘边取mod if( (tmp-1)%n==0)break; } if(i<=n-2)return 0; if( (tmp*num-1)%n==0)return 1; else return 0; } int main() { int t; while(scanf("%d",&n)!=EOF){ int times=0; for(int i=1;i<n;i++){ if(judge(i)==1)times++; } printf("%d\n",times); } }