Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.BigInteger;
- import java.util.Scanner;
- public class Main {
- public static BigInteger sqrtN(BigInteger in) {
- final BigInteger TWO = BigInteger.valueOf(2);
- int c;
- BigInteger n0 = TWO.pow(in.bitLength() / 2);
- BigInteger np = in;
- do {
- n0 = n0.add(in.divide(n0)).divide(TWO);
- c = np.compareTo(n0);
- np = n0;
- } while (c != 0);
- return n0;
- }
- static BigInteger getGCD(BigInteger a, BigInteger b) {
- return b.equals(BigInteger.ZERO) ? a : getGCD(b, a.mod(b));
- }
- static boolean isCoprime(BigInteger a, BigInteger b) {
- return getGCD(a, b).equals(BigInteger.ONE);
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int caseNo = 0;
- BigInteger n, e, d, p, q;
- BigInteger sqrtn, lower, temp, m, phi;
- while(in.hasNextBigInteger()) {
- n = in.nextBigInteger();
- e = in.nextBigInteger();
- d = in.nextBigInteger();
- if(n.equals(BigInteger.ZERO) && e.equals(BigInteger.ZERO) && d.equals(BigInteger.ZERO))
- break;
- temp = e.multiply(d);
- // lower = temp.divide(n);
- for(BigInteger i = BigInteger.ONE; ; i = i.add(BigInteger.ONE)) {
- if( (temp.mod(i)).equals(BigInteger.ONE) ) {
- phi = (temp.subtract(BigInteger.ONE)).divide(i);
- if( isCoprime(phi, e) && phi.compareTo(n) == -1)
- break;
- }
- }
- m = (n.subtract(phi).add(BigInteger.ONE)).divide(BigInteger.valueOf(2));
- sqrtn = sqrtN((m.pow(2)).subtract(n));
- p = m.subtract(sqrtn);
- q = m.add(sqrtn);
- ++caseNo;
- System.out.println("Case #" + caseNo + ": " + p + " " + q);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement