結果
問題 | No.152 貯金箱の消失 |
ユーザー | threepipes_s |
提出日時 | 2015-02-16 00:39:34 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 118 ms / 5,000 ms |
コード長 | 2,398 bytes |
コンパイル時間 | 2,160 ms |
コンパイル使用メモリ | 78,976 KB |
実行使用メモリ | 51,352 KB |
最終ジャッジ日時 | 2024-06-23 20:37:17 |
合計ジャッジ時間 | 3,638 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 54 ms
50,424 KB |
testcase_01 | AC | 52 ms
49,960 KB |
testcase_02 | AC | 54 ms
50,408 KB |
testcase_03 | AC | 54 ms
50,480 KB |
testcase_04 | AC | 56 ms
50,512 KB |
testcase_05 | AC | 56 ms
50,304 KB |
testcase_06 | AC | 58 ms
50,040 KB |
testcase_07 | AC | 74 ms
51,156 KB |
testcase_08 | AC | 116 ms
51,208 KB |
testcase_09 | AC | 118 ms
51,308 KB |
testcase_10 | AC | 106 ms
51,340 KB |
testcase_11 | AC | 89 ms
51,352 KB |
ソースコード
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.TreeSet; public class Main { public static boolean result[]; public static int dp[][]; public static void main(String[] args) throws NumberFormatException, IOException{ ContestScanner in = new ContestScanner(); long n = in.nextLong()/4; long count = 0; long mod = 1000003; // TreeSet<Integer> set = new TreeSet<Integer>(); int max; for(max=1; max*max<=n; max++); for(int i=1; i<max; i++){ for(int j=i+1; j<=max; j++){ if((j-i)%2 == 0) continue; if(gcd(i,j) != 1) continue; int a = i*i+j*j; int b = 2*i*j; int c = j*j-i*i; if(a+b+c <= n){ // if(!set.contains(a+b+c)){ // set.add(a+b+c); // System.err.println(a+" "+b+" "+c); count++; if(count >= mod) count%=mod; // } } } } System.out.println(count); } static int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } } class MyComp implements Comparator<int[]>{ public int compare(int[] a, int[] b) { return a[0] - b[0]; } } class Reverse implements Comparator<Integer>{ public int compare(Integer arg0, Integer arg1) { return arg1 - arg0; } } class Node{ int id; List<Node> edge = new ArrayList<Node>(); public Node(int id){ this.id = id; } public void createEdge(Node node){ edge.add(node); } } class ContestScanner{ private BufferedReader reader; private String[] line; private int idx; public ContestScanner() throws FileNotFoundException{ reader = new BufferedReader(new InputStreamReader(System.in)); } public ContestScanner(String filename) throws FileNotFoundException{ reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename))); } public String nextToken() throws IOException{ if(line == null || line.length <= idx){ line = reader.readLine().trim().split(" "); idx = 0; } return line[idx++]; } public long nextLong() throws IOException, NumberFormatException{ return Long.parseLong(nextToken()); } public int nextInt() throws NumberFormatException, IOException{ return (int)nextLong(); } public double nextDouble() throws NumberFormatException, IOException{ return Double.parseDouble(nextToken()); } }