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