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; }