首页 > 代码库 > URAL 1204. Idempotents 扩展欧几里德
URAL 1204. Idempotents 扩展欧几里德
题目来源:URAL 1204. Idempotents
题意:输入n(n = p*q p,q是质数) 并且x*x=x(mod n) 求x
思路: x*x=x(mod n) -> x*x+k*n=x -> x*(x-1)/n = k 所以 0 和 1 是一组解 因为n = p*q 且x*(x-1)%(p*q)== 0 x < n 因为x*x%n == x 模n之后才是x
1.x有p因子x-1有q因子
x%p == 0且(x-1)%q == 0
a*p == x且b*q == x-1 得到a*p-b*q == 1 gcd(p, q) == 1 用扩展欧几里德解出a, x ==a*p就是答按 在使他大于0
2.x-1有p因子x有q因子 x%p == 0 同上
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; void gcd(int a, int b, int& d, int& x, int& y) { if(!b) { d = a; x = 1; y = 0; } else { gcd(b, a%b, d, y, x); y -= x * (a/b); } } bool prime(int x) { for(int i = 2; i*i <= x; i++) { if(x%i == 0) return false; } return true; } int main() { int T; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); int p, q; for(int i = 2; i*i <= n; i++) { if(n%i == 0 && prime(i) && prime(n/i)) { p = i; q = n/i; break; } } int x, y, d; gcd(p, q, d, x, y); int x1 = p*x; if(x1 < 0) x1 += n; gcd(q, p, d, x, y); int x2 = q*x; if(x2 < 0) x2 += n; if(x1 > x2) swap(x1, x2); printf("%d %d %d %d\n", 0, 1, x1, x2); } return 0; }
URAL 1204. Idempotents 扩展欧几里德
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。