fork download
  1. import java.util.BitSet;
  2.  
  3. //mevius.5ch.net/test/read.cgi/tech/1480579110/807
  4. class Q9_807
  5. {
  6. public static void main(String[] args)
  7. {
  8. new Q9_807(10000);
  9. }
  10.  
  11. // 一辺の最大長
  12. final int n;
  13.  
  14. // ピタゴラス数の短辺・長辺ペアを入れるセット配列
  15. final BitSet[] set;
  16.  
  17. Q9_807(int n)
  18. {
  19. this.n = n;
  20. this.set = new BitSet[n + 1];
  21.  
  22. // (3,4,5)のピタゴラス数を親に一辺(斜辺を除く)がn以下のピタゴラス数のペアをすべてセット配列に入れる
  23. p(3, 4, 5);
  24.  
  25. // 収集したピタゴラス数の短辺長辺ペアから3個の数値がそれぞれペアになるものを探す
  26. for (int a = 0; a <= n; a++)
  27. {
  28. // 1個目の数値は短辺がa
  29. if (set[a] == null) continue;
  30.  
  31. // 2個目の数値は短辺aとセットになっている長辺b
  32. for (int b = set[a].nextSetBit(0); b >= 0; b = set[a].nextSetBit(b + 1))
  33. {
  34. // bが短辺になっているピタゴラス数がない場合は次に行く
  35. if (set[b] == null) continue;
  36.  
  37. // bitsetのandでaとbに共通する数値を取り出す
  38. BitSet bs = (BitSet) set[a].clone();
  39. bs.and(set[b]);
  40.  
  41. // 短辺a長辺c、短辺b長辺cのピタゴラス数があれば出力
  42. for (int c = bs.nextSetBit(0); c >= 0; c = bs.nextSetBit(c + 1))
  43. {
  44. System.out.printf("%d, %d, %d%n", a, b, c);
  45. }
  46. }
  47. }
  48. }
  49.  
  50. /**
  51.   * @param a 短辺
  52.   * @param b 長辺
  53.   * @param c 斜辺
  54.   */
  55. void p(int a, int b, int c)
  56. {
  57. // 長辺がnより大きい場合は何もしない
  58. if (b > n) return;
  59.  
  60. // a,bとその整数倍のピタゴラス数のペアを登録する
  61. for (int aa = a, bb = b; bb <= n; aa += a, bb += b)
  62. {
  63. if (set[aa] == null) set[aa] = new BitSet();
  64. set[aa].set(bb);
  65. }
  66.  
  67. // a,b,cを親に子ピタゴラス数を作る
  68. // 詳しくは ピタゴラス数 行列 とかで検索してください
  69. // (短辺, 長辺, 斜辺)になるように順番をちょっと調整してある
  70. p(a - 2 * b + 2 * c, 2 * a - b + 2 * c, 2 * a - 2 * b + 3 * c);
  71. p(2 * a + b + 2 * c, a + 2 * b + 2 * c, 2 * a + 2 * b + 3 * c);
  72. p(-2 * a + b + 2 * c, -a + 2 * b + 2 * c, -2 * a + 2 * b + 3 * c);
  73. }
  74. }
Success #stdin #stdout 0.17s 51400KB
stdin
Standard input is empty
stdout
44, 117, 240
85, 132, 720
88, 234, 480
132, 351, 720
140, 480, 693
160, 231, 792
170, 264, 1440
176, 468, 960
187, 1020, 1584
195, 748, 6336
220, 585, 1200
240, 252, 275
255, 396, 2160
264, 702, 1440
280, 960, 1386
308, 819, 1680
320, 462, 1584
340, 528, 2880
352, 936, 1920
374, 2040, 3168
396, 1053, 2160
420, 1440, 2079
425, 660, 3600
429, 880, 2340
440, 1170, 2400
480, 504, 550
480, 693, 2376
484, 1287, 2640
495, 4888, 8160
510, 792, 4320
528, 1404, 2880
528, 5796, 6325
560, 1920, 2772
561, 3060, 4752
572, 1521, 3120
595, 924, 5040
616, 1638, 3360
640, 924, 3168
660, 1755, 3600
680, 1056, 5760
700, 2400, 3465
704, 1872, 3840
720, 756, 825
748, 1989, 4080
748, 4080, 6336
765, 1188, 6480
780, 2475, 2992
792, 2106, 4320
800, 1155, 3960
828, 2035, 3120
832, 855, 2640
836, 2223, 4560
840, 2880, 4158
850, 1320, 7200
858, 1760, 4680
880, 2340, 4800
924, 2457, 5040
935, 1452, 7920
935, 5100, 7920
960, 1008, 1100
960, 1386, 4752
968, 2574, 5280
980, 3360, 4851
1008, 1100, 1155
1012, 2691, 5520
1020, 1584, 8640
1056, 2808, 5760
1100, 2925, 6000
1105, 1716, 9360
1120, 1617, 5544
1120, 3840, 5544
1122, 6120, 9504
1144, 3042, 6240
1155, 6300, 6688
1188, 3159, 6480
1200, 1260, 1375
1232, 3276, 6720
1260, 4320, 6237
1276, 3393, 6960
1280, 1848, 6336
1287, 2640, 7020
1320, 3510, 7200
1364, 3627, 7440
1400, 4800, 6930
1408, 3744, 7680
1440, 1512, 1650
1440, 2079, 7128
1452, 3861, 7920
1496, 3978, 8160
1540, 4095, 8400
1540, 5280, 7623
1560, 2295, 5984
1560, 4950, 5984
1575, 1672, 9120
1584, 4212, 8640
1600, 2310, 7920
1628, 4329, 8880
1656, 4070, 6240
1664, 1710, 5280
1672, 4446, 9120
1680, 1764, 1925
1680, 5760, 8316
1716, 3520, 9360
1716, 4563, 9360
1755, 4576, 6732
1760, 2541, 8712
1760, 4680, 9600
1804, 4797, 9840
1820, 6240, 9009
1920, 2016, 2200
1920, 2772, 9504
1960, 6720, 9702
2016, 2200, 2310
2160, 2268, 2475
2340, 7425, 8976
2400, 2520, 2750
2484, 6105, 9360
2496, 2565, 7920
2640, 2772, 3025
2880, 3024, 3300
2964, 9152, 9405
3024, 3300, 3465
3120, 3276, 3575
3360, 3528, 3850
3600, 3780, 4125
3840, 4032, 4400
4032, 4400, 4620
4080, 4284, 4675
4320, 4536, 4950
4560, 4788, 5225
4800, 5040, 5500
5040, 5292, 5775
5040, 5500, 5775
5280, 5544, 6050
5520, 5796, 6325
5760, 6048, 6600
6000, 6300, 6875
6048, 6600, 6930
6240, 6552, 7150
6480, 6804, 7425
6720, 7056, 7700
6960, 7308, 7975
7056, 7700, 8085
7200, 7560, 8250
7440, 7812, 8525
7680, 8064, 8800
7920, 8316, 9075
8064, 8800, 9240
8160, 8568, 9350
8400, 8820, 9625
8640, 9072, 9900