結果
問題 | No.1063 ルートの計算 / Sqrt Calculation |
ユーザー | hiromi_ayase |
提出日時 | 2020-05-29 21:29:56 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 175 ms / 2,000 ms |
コード長 | 3,012 bytes |
コンパイル時間 | 2,539 ms |
コンパイル使用メモリ | 84,508 KB |
実行使用メモリ | 43,572 KB |
最終ジャッジ日時 | 2024-04-23 20:17:01 |
合計ジャッジ時間 | 5,726 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 175 ms
43,380 KB |
testcase_01 | AC | 164 ms
42,984 KB |
testcase_02 | AC | 162 ms
43,044 KB |
testcase_03 | AC | 166 ms
43,004 KB |
testcase_04 | AC | 172 ms
43,308 KB |
testcase_05 | AC | 161 ms
43,080 KB |
testcase_06 | AC | 162 ms
43,144 KB |
testcase_07 | AC | 145 ms
43,572 KB |
testcase_08 | AC | 151 ms
43,188 KB |
testcase_09 | AC | 175 ms
43,056 KB |
testcase_10 | AC | 144 ms
43,300 KB |
testcase_11 | AC | 160 ms
43,216 KB |
testcase_12 | AC | 166 ms
43,408 KB |
testcase_13 | AC | 161 ms
43,296 KB |
testcase_14 | AC | 165 ms
43,312 KB |
testcase_15 | AC | 161 ms
43,516 KB |
testcase_16 | AC | 161 ms
43,240 KB |
ソースコード
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] primes = sieveEratosthenes(1000000); int[][] f = factor(n, primes); int ret1 = 1; int ret2 = 1; for (int[] v : f) { if (v[1] % 2 == 1) { ret2 *= v[0]; v[1]--; } for (int i = 0; i < v[1] / 2; i++) { ret1 *= v[0]; } } System.out.println(ret1 + " " + ret2); } public static int[][] factor(int n, int[] primes) { int[][] ret = new int[9][2]; int rp = 0; for (int p : primes) { if (p * p > n) break; int i; for (i = 0; n % p == 0; n /= p, i++) ; if (i > 0) { ret[rp][0] = p; ret[rp][1] = i; rp++; } } if (n != 1) { ret[rp][0] = n; ret[rp][1] = 1; rp++; } return Arrays.copyOf(ret, rp); } public static int[] sieveEratosthenes(int n) { if (n <= 32) { int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 }; for (int i = 0; i < primes.length; i++) { if (n < primes[i]) { return Arrays.copyOf(primes, i); } } return primes; } int u = n + 32; double lu = Math.log(u); int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)]; ret[0] = 2; int pos = 1; int[] isnp = new int[(n + 1) / 32 / 2 + 1]; int sup = (n + 1) / 32 / 2 + 1; int[] tprimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 }; for (int tp : tprimes) { ret[pos++] = tp; int[] ptn = new int[tp]; for (int i = (tp - 3) / 2; i < tp << 5; i += tp) ptn[i >> 5] |= 1 << i; for (int j = 0; j < sup; j += tp) { for (int i = 0; i < tp && i + j < sup; i++) { isnp[j + i] |= ptn[i]; } } } // 3,5,7 // 2x+3=n int[] magic = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17, 9, 6, 16, 5, 15, 14 }; int h = n / 2; for (int i = 0; i < sup; i++) { for (int j = ~isnp[i]; j != 0; j &= j - 1) { int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27]; int p = 2 * pp + 3; if (p > n) break; ret[pos++] = p; if ((long) p * p > n) continue; for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q; } } return Arrays.copyOf(ret, pos); } }