首页 > 代码库 > URAL 1268. Little Chu 求最大原根
URAL 1268. Little Chu 求最大原根
题目来源:URAL 1268. Little Chu
题意:输入n 求一个最大的k 使得k^1 k^2 k^3...k^x mod n 后各不相同
思路:mod n 后各不相同 最多有 n个 那么此事k就是原根 因为k <= n 所以从n开始向下枚举 求一个最大的原根
#include <cstdio> #include <cstring> 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; }
URAL 1268. Little Chu 求最大原根
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。