• API
• FAQ
• Tools
• Archive
SHARE
TWEET Untitled a guest Mar 26th, 2019 57 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;
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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top