Description

A square root of a number x is a number r such that r² = x. A discrete square root of a non-negative integerx is a non-negative integer r such that r² 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

思路：已知一个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,这个也是未知数，当我们验证r1+K1*A=r的时候

可以叠加Ax来表示K的变化，并找结果

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         typedef long long ll;; using namespace std; const int maxn = 11111; int N, r; set
        
          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
         
          ::iterator it; printf("Case %d:", cas++); for (it = ans.begin(); it != ans.end(); it++) printf(" %lld", *it); printf("\n"); } return 0; }