SHARE
TWEET

Untitled

a guest Mar 26th, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. public class Solution {
  5.    
  6.     private static int getSquareRoot(long a) {
  7.         long f = 0;
  8.         int ret = 0;
  9.         for(long i = 0; i < 16; i++) {
  10.             ret <<= 1;
  11.             long kari_f = (f + 1) << ((15 - i) * 2);
  12.             if(a >= kari_f) {
  13.                 f = f + 2;
  14.                 a -= kari_f;
  15.                 ret++;
  16.             }
  17.             f <<= 1;
  18.         }
  19.         return ret;
  20.     }
  21.    
  22.     private static int combinations(int a, int b_c) {
  23.         if(2 * a < b_c) {
  24.             return 0;
  25.         }
  26.         if(a >= b_c) {
  27.             return b_c / 2;
  28.         }
  29.         return a - (b_c - 1) / 2;
  30.     }
  31.    
  32.     private static int gcd(int a, int b) {
  33.         while(a != 0) {
  34.             int temp = a;
  35.             a = b % a;
  36.             b = temp;
  37.         }
  38.         return b;
  39.     }
  40.    
  41.     private static long[] countAll(int limit) {
  42.         long[] solutions = new long[limit + 1];
  43.         for(int m = 1; m <= getSquareRoot(2 * limit); m++) {
  44.             for(int n = 1; n < m; n++) {
  45.                 if((m % 2) != (n % 2) && gcd(m, n) == 1) {
  46.                     int x = m * m - n * n;
  47.                     int y = 2 * m * n;
  48.                     for(int k = 1; k * x <= limit; k++) {
  49.                         solutions[k * x] += combinations(k * x, k * y);
  50.                     }
  51.                     for(int k = 1; k * y <= limit; k++) {
  52.                         solutions[k * y] += combinations(k * y, k * x);
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.         return solutions;
  58.     }
  59.    
  60.     public static void main(String[] args) {
  61.         long[] solutions = countAll((int) Math.pow(10, 6));
  62.         ArrayList<Long> total = new ArrayList<>();
  63.         long sum = 0;
  64.         for(long i : solutions) {
  65.             sum += i;
  66.             total.add(sum);
  67.         }
  68.         try(Scanner sc = new Scanner(System.in)) {
  69.             int T = sc.nextInt();
  70.             while(T-- > 0) {
  71.                 int N = sc.nextInt();
  72.                 System.out.println(total.get(N));
  73.             }
  74.         }
  75.     }
  76. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top