首页 > 代码库 > UVA - 1426 Discrete Square Roots (模方程)

UVA - 1426 Discrete Square Roots (模方程)

2024-07-19 10:54:05   232人阅读

Description

Download as PDF

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 $ \equiv$x mod N , 0$ \le$r <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. (1$ \le$x <N, 2$ \le$N < 1, 000, 000, 000, 1$ \le$r < 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 (模方程)


联系
我们