题目链接：
URAL 1226 Little Chu*
题意：
找到最大的k,使得k, k^2, k^3…k^x 模n的结果各不相同且x尽可能大。
分析：
求最大原根。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 70000;int T, n, prime_cnt, factor_cnt;
int prime[MAX_N], factor[MAX_N];
bitset<MAX_N> bs;void GetPrime()
{bs.set();prime_cnt = 0;for(int i = 2; i < MAX_N; i++){if(bs[i] == 1) { prime[prime_cnt++] = i; }for(int j = 0; j < prime_cnt && i * prime[j] < MAX_N; j++){bs[i * prime[j]] = 0;if(i % prime[j] == 0) break;}}
}void GetFactor(int x)
{factor_cnt = 0;for(int i = 0; i < prime_cnt && prime[i] * prime[i] <= x; i++){if(x % prime[i] == 0){factor[factor_cnt++] = prime[i];while(x % prime[i] == 0){x /= prime[i];}}}if(x > 1){factor[factor_cnt++] = x;}
}int quick_pow(int a, int b, int m)
{ll res = 1, tmp = (ll)a, mod = (ll)m;while(b){if(b & 1) res = res * tmp % mod;tmp = tmp * tmp % mod;b >>= 1;}return (int)res;
}int main()
{GetPrime();scanf("%d", &T);while(T--){scanf("%d", &n);GetFactor(n - 1);int ans ;for(int i = n - 1; i >= 2; i--){int flag = true;for(int j = 0; j < factor_cnt; j++){if(quick_pow(i, (n - 1) / factor[j], n) == 1){flag = false;//printf("i = %d factor[j] = %d\n", i, factor[j]);break;}}if(flag){ans = i;break;}}printf("%d\n", ans);}return 0;
}