首页 > 代码库 > UVA - 1426 Discrete Square Roots (模方程)
UVA - 1426 Discrete Square Roots (模方程)
Description
A square root of a number x is a number r such that r2 = x. A discrete square root of a non-negative integerx is a non-negative integer r such that r2 x mod N , 0r <N , where N is a specific positive integer and mod is the modulo operation.
It is well-known that any positive real number has exactly two square roots, but a non-negative integer may have more than two discrete square roots. For example, forN = 12 , 1 has four discrete square roots 1, 5, 7 and 11.
Your task is to find all discrete square roots of a given non-negative integerx. To make it easier, a known square root r of x is also given to you.
Input
The input consists of multiple test cases. Each test case contains exactly one line, which gives three integersx, N and r. (1x <N, 2N < 1, 000, 000, 000, 1r < N). It is guaranteed that r is a discrete square root ofx modulo N. The last test case is followed by a line containing three zeros.
Output
For each test case, print a line containing the test case number (beginning with 1) followed by a list of corresponding discrete square roots, in which all numbers are sorted increasingly..
Sample Input
1 12 1 4 15 2 0 0 0
Sample Output
Case 1: 1 5 7 11 Case 2: 2 7 8 13
题意:r^2≡x(mod n)求(0<r<n)r的所有解
思路:已知一个x,n和一个解r1,假设还有一个解是r,那么就可以通过:r^2≡x(mod n) 和:r1^2≡x(mod n)
得到::r1^2 + k1*n=x 和 :r^2 + k2*n=x,连立解得:r^2 - r1^2 = k3*n =>(r+r1)*(r-r1) = k3*n
那么我们假设A*B = n,我们就可以得到::r+r1≡0(mod A) ,:r-r1≡0(mod B),也就可以得到:
r1+K1*A = r1-K2*B = r,变形得到:K1*A≡2*r1(mod B),那么这个就是解模方程了,但是我们带入系数的时候,
是带入A和B,这个通过枚举N的因子就可以得到了,因为还有一个K1,这个就留着我们最后放方程都扩大K1倍的时候
解决.
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include <vector> typedef long long ll;; using namespace std; const int maxn = 11111; int N, r; set<ll> ans; void exgcd(ll a, ll b, ll &d, ll &x, ll &y) { if (b == 0) { d = a; x = 1, y = 0; } else { exgcd(b, a%b, d, y, x); y -= a / b * x; } } void solve(ll c, ll a, ll b) { ll x, y, d; exgcd(a, b, d, x, y); ll n = 2*r; if (n % d == 0) { x *= n / d; x = (x % (b/d) + (b/d)) % (b/d); ll m = x * a - r; while (m < N) { if (m >= 0 && m * m % N == c) ans.insert(m); m += b / d * a; } } } int main() { int x, cas = 1; while (scanf("%d%d%d", &x, &N, &r) != EOF && x) { ans.clear(); for (int i = 1; i*i <= N; i++) if (N % i == 0) { solve(x, i, N/i); solve(x, N/i, i); } set<ll>::iterator it; printf("Case %d:", cas++); for (it = ans.begin(); it != ans.end(); it++) printf(" %lld", *it); printf("\n"); } return 0; }
UVA - 1426 Discrete Square Roots (模方程)