题目来源：URAL 1268. Little Chu

题意：输入n 求一个最大的k 使得k^1 k^2 k^3...k^x mod n 后各不相同

思路：mod n 后各不相同 最多有 n个 那么此事k就是原根 因为k <= n 所以从n开始向下枚举 求一个最大的原根

#include 
  
   
#include 
   
     using namespace std; typedef long long LL; int p[100000], c; LL pow_mod(LL a, LL x, LL m) { LL ans = 1; while(x) { if(x&1) ans = ans * a % m; a = a * a % m; x >>= 1; } return ans; } bool ok(int x, int ph, int m) { for(int i = 0; i < c; i++) if(pow_mod(x, ph/p[i], m) == 1) return false; return true; } void divide(int x) { c = 0; for(int i = 2; i*i <= x; i++) { if(x % i == 0) { p[c++] = i; while(x % i == 0) x /= i; } } if(x > 1) p[c++] = x; } int main() { int T; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); int m = n, ans = m; for(int i = 2; i*i <= n; i++) { if(n%i == 0) { ans = ans / i * (i-1); while(n%i == 0) n /= i; } } if(n > 1) ans = ans / n * (n-1); //printf("%d\n", ans); divide(ans); int x = ans; while(!ok(x, ans, m)) x--; printf("%d\n", x); } return 0; }