UVA 1426 - Discrete Square Roots

题意：给定X， N。 R。要求r2≡x (mod n) (1 <= r < n)的全部解。R为一个已知解

思路：

r2≡x (mod n)=>r2+k1n=x

已知一个r!，带入两式相减得 r2−r12=kn => (r+r1)(r−r1)=kn

枚举A，B,使得

A * B = n

(r + r1)为A倍数

(r - r1)为B倍数

这样就能够推出

Aka−r1=Bkb+r1=r

=> Aka=Bkb+2r1

=> Aka≡2r1 (mod B)

这样就等于求线性模方程的全部解。进而求出还有一解R。最后把全部答案用一个set保存下来输出

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;long long X, N, R;set
         
           ans;long long exgcd(long long a, long long b, long long &x, long long &y) {    if (!b) {x = 1; y = 0; return a;}    long long d = exgcd(b, a % b, y, x);    y -= a / b * x;    return d;}void mod_line(long long a, long long b, long long n) {    long long x, y;    long long d = exgcd(a, n, x, y);    if (b % d) return;    x = x * (b / d);    x = (x % (n / d) + (n / d)) % (n / d);    long long a0 = x * a - b / 2;    long long k = a * n / d;    for (long long tmp = a0; tmp < N; tmp += k) {	if (tmp >= 0) ans.insert(tmp);    }}int main() {    int cas = 0;    while (~scanf("%lld%lld%lld", &X, &N, &R) && N) {	ans.clear();	long long m = (long long)sqrt(N);	for (long long i = 1; i <= m; i++) {	    if (N % i) continue;	    mod_line(i, 2 * R, N / i);	    mod_line(N / i, 2 * R, i);	}	printf("Case %d:", ++cas);	for (set
          
           ::iterator it = ans.begin(); it != ans.end(); it++) printf(" %lld", *it); printf("\n"); } return 0;}