fork download 
  1. //mevius.5ch.net/test/read.cgi/tech/1480579110/858
  2. //与えられた自然数を高々四個の四角数(平方数)の和で表せ
  3.  
  4. import java.util.*;
  5. import java.lang.*;
  6. import java.io.*;
  7.  
  8. class Q9_858
  9. {
  10.     public static void main(String[] args)
  11.     {
  12.         try (Scanner in = new Scanner(System.in))
  13.         {
  14.             while (in.hasNextInt())
  15.             {
  16.                 System.out.println(calc(in.nextInt()));
  17.             }
  18.         }
  19.     }
  20.  
  21.     static String calc(int n)
  22.     {
  23.         int sqrtN = (int) Math.sqrt(n);
  24.         if (sqrtN * sqrtN == n) return String.format("%d = %d^2", n, sqrtN);
  25.  
  26.         BitSet bs1 = new BitSet();
  27.         BitSet bs2 = new BitSet();
  28.         for (int i = 1; i <= sqrtN; i++)
  29.         {
  30.             int ii = i * i;
  31.             bs1.set(ii);
  32.             if (bs1.get(n - ii)) return String.format("%d = %d^2 + %d^2", n, (int) Math.sqrt(n - ii), i);
  33.  
  34.             for (int j = 1, k = (int) Math.sqrt(n - ii); j <= k; j++)
  35.             {
  36.                 int jj = j * j;
  37.                 int p = ii + jj;
  38.                 try
  39.                 {
  40.                     bs2.set(p);
  41.                 } catch (IndexOutOfBoundsException ioobe)
  42.                 {
  43.                     System.out.println(ii + "," + jj + "," + p);
  44.                     throw ioobe;
  45.                 }
  46.                 if (bs1.get(n - p)) { return String.format("%d = %d^2 + %d^2 + %d^2", n, (int) Math.sqrt(n - p), i, j); }
  47.                 if (bs2.get(n - p)) { return String.format("%d = %s + %d^2 + %d^2", n, toString2(bs1, n - p), i, j); }
  48.             }
  49.         }
  50.  
  51.         throw new RuntimeException();
  52.     }
  53.  
  54.     private static String toString2(BitSet bs, int i)
  55.     {
  56.         for (int j = 1; j * j < i; j++)
  57.         {
  58.             if (bs.get(i - j * j)) return String.format("%d^2 + %d^2", j, (int) Math.sqrt(i - j * j));
  59.         }
  60.  
  61.         throw new IllegalArgumentException();
  62.     }
  63. }
  64.  
Success #stdin #stdout 0.32s 303024KB
comments (?)
stdin 
1
2
3
4
5
6
7
8
9
10
100
111
150
200
255
257
65535
65537
4891817
5461418
123456789
123997897
897154611
stdout 
1 = 1^2
2 = 1^2 + 1^2
3 = 1^2 + 1^2 + 1^2
4 = 2^2
5 = 1^2 + 2^2
6 = 1^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
8 = 2^2 + 2^2
9 = 3^2
10 = 2^2 + 1^2 + 1^2 + 2^2
100 = 10^2
111 = 3^2 + 1^2 + 1^2 + 10^2
150 = 2^2 + 1^2 + 1^2 + 12^2
200 = 12^2 + 2^2 + 4^2 + 6^2
255 = 15^2 + 1^2 + 2^2 + 5^2
257 = 12^2 + 2^2 + 3^2 + 10^2
65535 = 142^2 + 1^2 + 1^2 + 213^2
65537 = 45^2 + 2^2 + 2^2 + 252^2
4891817 = 2176^2 + 3^2 + 4^2 + 396^2
5461418 = 354^2 + 1^2 + 1^2 + 2310^2
123456789 = 9424^2 + 1^2 + 4^2 + 5886^2
123997897 = 9316^2 + 4^2 + 5^2 + 6100^2
897154611 = 10897^2 + 1^2 + 1^2 + 27900^2
https://ideone.com/ND4D2n
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!