题意:给定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 <stdio.h> #include <string.h> #include <math.h> #include <set> using namespace std; long long X, N, R; set<long long> 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<long long>::iterator it = ans.begin(); it != ans.end(); it++) printf(" %lld", *it); printf("\n"); } return 0; }
UVA 1426 - Discrete Square Roots(数论),布布扣,bubuko.com
UVA 1426 - Discrete Square Roots(数论)
原文:http://blog.csdn.net/accelerator_/article/details/36669087