1426 - Discrete Square Roots

Time limit: 3.000 seconds

A square root of a number x <tex2html_verbatim_mark>is a number r <tex2html_verbatim_mark>such that r² = x <tex2html_verbatim_mark>. A discrete square root of a non-negative integer x <tex2html_verbatim_mark>is a non-negative integer r <tex2html_verbatim_mark>such thatr²  x mod N <tex2html_verbatim_mark>, 0r < N <tex2html_verbatim_mark>, where N <tex2html_verbatim_mark>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, for N = 12 <tex2html_verbatim_mark>, 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 integer x <tex2html_verbatim_mark>. To make it easier, a known square root r <tex2html_verbatim_mark>of x <tex2html_verbatim_mark>is also given to you.

 

Input 

The input consists of multiple test cases. Each test case contains exactly one line, which gives three integers x <tex2html_verbatim_mark>, N <tex2html_verbatim_mark>and r <tex2html_verbatim_mark>. (1x < N, 2N < 1, 000, 000, 000, 1r < N) <tex2html_verbatim_mark>. It is guaranteed that r <tex2html_verbatim_mark>is a discrete square root of x<tex2html_verbatim_mark>modulo N <tex2html_verbatim_mark>. 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
    

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long LL;set
          
            s;LL X,R,N;LL Extended_Euclid(LL a,LL b,LL &x,LL &y)//欧几里德扩展定理 { LL d,t; if(b==0) { x=1;y=0;return a; } d=Extended_Euclid(b,a%b,x,y); t=x; x=y; y=t-a/b*y; return d;}void Mod_Line_Equation_Solve(LL a,LL b,LL n)//模线性方程求解 { LL x,y,d,t,lcm; d=Extended_Euclid(a,n,x,y); if(b%d==0) { x=x*b/d; x=(x%(n/d)+n/d)%(n/d); t=a*x-b/2; lcm=a/d*n; for(;t
           
            =0 && t*t%N==X) s.insert(t);//符合条件的解插入set容器 } }}int main(){ LL i,top,Case=0; while(cin>>X>>N>>R && !(X==0 && N==0 && R==0)) { Case++; printf("Case %d:",Case); s.clear(); top=sqrt(N+0.5); for(i=1;i<=top;i++)//枚举所有的A*B=n的情况 { if(N%i==0) { Mod_Line_Equation_Solve(i,2*R,N/i); Mod_Line_Equation_Solve(N/i,2*R,i); } } set
            
             ::iterator it; for(it=s.begin();it!=s.end();it++) printf(" %lld",*it); printf("\n"); } return 0;}