首页 > 代码库 > URAL 1204. Idempotents (扩展欧几里得)
URAL 1204. Idempotents (扩展欧几里得)
题目链接
题意 ： 给你一个同余方程， x*x ≡ x (mod n)，让你求出所有的小于n的x。
思路 ：
先来看同余的概念 ：给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即m|(a-b)，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。
因此题目中给定的式子可以写成：(x*x-x)/n=k.也就是说(x*x-x)是n的整数倍，取余n是0.
因为n=p*q，而且gcd(p,q)=1 ;所以上式可以写为，x*(x-1)/(p*q)=k.
让我们分情况讨论：
上式中，
- 当k=0时，要么x为0，要么x-1为0，所以，两个解已经出来了，0和1。
- 当k!=0时，要么p是x的因数并且q是x-1的因数，要么q是x的因数，p是x-1的因数。因此，这种情况下只要求出两种情况的p和q，然后再求他们的倍数。
x是不可能同时存在p和q两个因子的，因为这样就大于n了。
对于第1种情况，设x是p的a倍，x-1是q的b倍，则p*a-q*b=1.也就是说，因为gcd(p,q)=1，所以p*a-q*b=gcd(p,q).
让我们再来看扩展欧几里得 ： 扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在）。
所以用扩展欧几里得将p*a-q*b=gcd(p,q).这个式子里的a求出来，然后乘上枚举出来的p。就是x的又一个解。最后再求第二种情况下的a即可。
#include <stdio.h>#include <iostream>using namespace std ;void exGcd(int a,int b,int& x,int& y){ if(b == 0) { x = 1 ; y = 0 ; return ; //return a; } exGcd(b,a%b,x,y); int t = x ; x = y ; y = t - a / b * y ; // return r;}bool isprime(int x){ for(int i = 2 ; i * i < x ; i++) { if(x % i == 0) return false; } return true ;}int main(){ int T,n,p,q,x,y ; scanf("%d",&T) ; while(T--) { scanf("%d",&n) ; for(int i = 2 ; i * i < n ; i++) { if( (n%i == 0) && isprime(i) && isprime(n/i) ) { p = i ; q = n/i ; break ; } } exGcd(p,q,x,y) ; int ans1 = p*x < 0 ? p*x+n : p*x ; exGcd(q,p,x,y) ; int ans2 = q*x < 0 ? q*x+n : q*x ; if(ans1 > ans2) swap(ans1,ans2) ; printf("0 1 %d %d\n",ans1,ans2) ; } return 0 ;}
URAL 1204. Idempotents (扩展欧几里得)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。