Guest User

List ocurrences of a[t] = c

a guest
Dec 12th, 2018
220
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.00 KB | None | 0 0
  1. import java.math.BigInteger;
  2. import java.util.Scanner;
  3.  
  4. public class List_a_of_t_eq_c {
  5.     private static BigInteger zero = BigInteger.ZERO;
  6.     private static BigInteger one = BigInteger.ONE;
  7.     private static BigInteger two = BigInteger.valueOf(2);
  8.     private static BigInteger four = BigInteger.valueOf(4);
  9.     private static BigInteger eight = BigInteger.valueOf(8);
  10.    
  11.     public static void main(String[] args) {
  12.         Scanner s = new Scanner(System.in);
  13.  
  14.         for (;;) {
  15.             BigInteger c = s.nextBigInteger();
  16.             BigInteger _2c = c.multiply(two);
  17.             BigInteger d = sqrt(c);
  18.             BigInteger e = c.subtract(d.pow(2));
  19.  
  20.             BigInteger t = one;
  21.             BigInteger e_t = _2c;
  22.  
  23.             BigInteger gap = four;
  24.             if (e.and(one).equals(zero)) {
  25.                 gap = four;
  26.             }
  27.  
  28.             while (!lt(e_t, _2c.negate())) {
  29.                 VQCElement occurrence = getRecord(e_t, one, t);
  30.  
  31.                 t = t.add(one);
  32.                 e_t = e_t.subtract(gap);
  33.  
  34.                 System.out.println(occurrence.toString());
  35.  
  36.                 gap = gap.add(eight);
  37.             }
  38.             System.out.println();
  39.         }
  40.     }
  41.  
  42.     private static VQCElement getRecord(BigInteger e, BigInteger n, BigInteger t) {
  43.         VQCElement v = new VQCElement();
  44.         v.e = e;
  45.         v.n = n;
  46.         v.t = t;
  47.  
  48.         v.x = getX(e, t);
  49.         v.a = (v.x.pow(2)).add(e).divide(two.multiply(v.n));
  50.         v.d = v.a.add(v.x);
  51.         v.b = v.a.add(two.multiply(v.x)).add(two.multiply(v.n));
  52.         v.c = v.a.multiply(v.b);
  53.  
  54.         return v;
  55.     }
  56.  
  57.     private static BigInteger getX(BigInteger e, BigInteger t) {
  58.         BigInteger subtrahend = one;
  59.  
  60.         if (e.and(one).equals(zero)) {
  61.             subtrahend = two;
  62.         }
  63.  
  64.         return two.multiply(t).subtract(subtrahend);
  65.     }
  66.  
  67.     public static boolean gt(BigInteger i, BigInteger i2) {
  68.         int result = i.compareTo(i2);
  69.  
  70.         return result > 0;
  71.     }
  72.  
  73.     private static boolean lt(BigInteger i, BigInteger i2) {
  74.         int result = i.compareTo(i2);
  75.  
  76.         return result < 0;
  77.     }
  78.  
  79.     /** define d(n) = sqrt(n)//1*/
  80.     private static BigInteger sqrt(BigInteger i) {
  81.         BigInteger n = zero;
  82.         BigInteger p = zero;
  83.  
  84.         if (i.equals(zero)) {
  85.             return zero;
  86.         } else if (i.equals(one)) {
  87.             return one;
  88.         } else if (i.equals(two)) {
  89.             return one;
  90.         } else if (i.equals(BigInteger.valueOf(3))) {
  91.             return one;
  92.         } else if (i.equals(BigInteger.valueOf(4))) {
  93.             return two;
  94.         } else if (i.equals(BigInteger.valueOf(5))) {
  95.             return two;
  96.         }
  97.  
  98.         BigInteger high = i.shiftRight(1);
  99.         BigInteger low = zero;
  100.  
  101.         //high > low + 1
  102.         while (gt(high, low.add(one))) {
  103.             //n = (high + low) >> 1;
  104.             n = (high.add(low)).shiftRight(1);
  105.             p = n.multiply(n);
  106.  
  107.             int result = i.compareTo(p);
  108.             if (result < 0) {
  109.                 high = n;
  110.             } else if (result > 0) {
  111.                 low = n;
  112.             } else {
  113.                 break;
  114.             }
  115.         }
  116.  
  117.         if (i.equals(p)) {
  118.             return n;
  119.         } else {
  120.             return low;
  121.         }
  122.     }
  123.  
  124.     @SuppressWarnings({"StringConcatenationInsideStringBufferAppend", "StringBufferReplaceableByString"})
  125.     static class VQCElement {
  126.         public BigInteger a;
  127.         public BigInteger b;
  128.         public BigInteger c;
  129.         public BigInteger d;
  130.         public BigInteger e;
  131.         public BigInteger i;
  132.         public BigInteger n;
  133.         public BigInteger x;
  134.         public BigInteger t;
  135.  
  136.  
  137.         public String getCoordinates() {
  138.             return "(" + e + ", " + n + ", " + t + ")";
  139.         }
  140.  
  141.         public String toString() {
  142.             return "{" + e + ":" + n + ":" + d + ":" + x + ":" + a + ":" + b + "} " + getCoordinates();
  143.         }
  144.     }
  145. }
Advertisement
Add Comment
Please, Sign In to add comment