Advertisement
Kaidul

1431

Jan 9th, 2014
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.70 KB | None | 0 0
  1. import java.math.BigInteger;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.  
  6.     public static BigInteger sqrtN(BigInteger in) {
  7.         final BigInteger TWO = BigInteger.valueOf(2);
  8.         int c;
  9.         BigInteger n0 = TWO.pow(in.bitLength() / 2);
  10.         BigInteger np = in;
  11.  
  12.         do {
  13.             n0 = n0.add(in.divide(n0)).divide(TWO);
  14.             c = np.compareTo(n0);
  15.             np = n0;
  16.         }  while (c != 0);
  17.         return n0;
  18.     }
  19.    
  20.     static BigInteger getGCD(BigInteger a, BigInteger b) {
  21.         return b.equals(BigInteger.ZERO) ? a : getGCD(b, a.mod(b));
  22.     }
  23.  
  24.     static boolean isCoprime(BigInteger a, BigInteger b) {
  25.         return getGCD(a, b).equals(BigInteger.ONE);
  26.     }
  27.    
  28.     public static void main(String[] args) {
  29.         Scanner in = new Scanner(System.in);
  30.         int caseNo = 0;
  31.         BigInteger n, e, d, p, q;
  32.         BigInteger sqrtn, lower, temp, m, phi;
  33.         while(in.hasNextBigInteger()) {
  34.             n = in.nextBigInteger();
  35.             e = in.nextBigInteger();
  36.             d = in.nextBigInteger();
  37.             if(n.equals(BigInteger.ZERO) && e.equals(BigInteger.ZERO) && d.equals(BigInteger.ZERO))
  38.                 break;
  39.             temp = e.multiply(d);
  40. //          lower = temp.divide(n);
  41.             for(BigInteger i = BigInteger.ONE; ; i = i.add(BigInteger.ONE)) {
  42.                 if( (temp.mod(i)).equals(BigInteger.ONE) ) {
  43.                     phi = (temp.subtract(BigInteger.ONE)).divide(i);
  44.                     if( isCoprime(phi, e) && phi.compareTo(n) == -1)
  45.                         break;
  46.                 }
  47.             }
  48.             m = (n.subtract(phi).add(BigInteger.ONE)).divide(BigInteger.valueOf(2));
  49.             sqrtn = sqrtN((m.pow(2)).subtract(n));
  50.             p = m.subtract(sqrtn);
  51.             q = m.add(sqrtn);
  52.             ++caseNo;
  53.             System.out.println("Case #" + caseNo + ": " + p + " " + q);
  54.         }
  55.     }
  56.  
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement