結果
問題 | No.847 Divisors of Power |
ユーザー | Grenache |
提出日時 | 2019-07-05 22:56:59 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 486 ms / 2,000 ms |
コード長 | 4,301 bytes |
コンパイル時間 | 4,273 ms |
コンパイル使用メモリ | 82,620 KB |
実行使用メモリ | 63,932 KB |
最終ジャッジ日時 | 2024-04-16 07:58:34 |
合計ジャッジ時間 | 10,230 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 137 ms
54,628 KB |
testcase_01 | AC | 135 ms
54,016 KB |
testcase_02 | AC | 139 ms
54,080 KB |
testcase_03 | AC | 139 ms
54,136 KB |
testcase_04 | AC | 142 ms
54,200 KB |
testcase_05 | AC | 143 ms
54,020 KB |
testcase_06 | AC | 145 ms
54,208 KB |
testcase_07 | AC | 144 ms
54,168 KB |
testcase_08 | AC | 147 ms
54,444 KB |
testcase_09 | AC | 142 ms
54,224 KB |
testcase_10 | AC | 140 ms
54,216 KB |
testcase_11 | AC | 147 ms
54,228 KB |
testcase_12 | AC | 143 ms
54,108 KB |
testcase_13 | AC | 148 ms
54,456 KB |
testcase_14 | AC | 145 ms
54,044 KB |
testcase_15 | AC | 402 ms
63,932 KB |
testcase_16 | AC | 137 ms
41,340 KB |
testcase_17 | AC | 141 ms
41,660 KB |
testcase_18 | AC | 145 ms
41,396 KB |
testcase_19 | AC | 159 ms
41,964 KB |
testcase_20 | AC | 140 ms
41,860 KB |
testcase_21 | AC | 239 ms
47,356 KB |
testcase_22 | AC | 125 ms
40,116 KB |
testcase_23 | AC | 137 ms
41,560 KB |
testcase_24 | AC | 486 ms
58,124 KB |
testcase_25 | AC | 140 ms
41,724 KB |
testcase_26 | AC | 136 ms
41,060 KB |
testcase_27 | AC | 138 ms
41,532 KB |
testcase_28 | AC | 122 ms
40,372 KB |
testcase_29 | AC | 122 ms
40,252 KB |
ソースコード
import java.io.*; import java.util.*; import java.util.Map.Entry; public class Main_yukicoder847 { private static Scanner sc; private static Printer pr; private static void solve() { int n = sc.nextInt(); int k = sc.nextInt(); int m = sc.nextInt(); Prime prime = new Prime((int)Math.sqrt(n)); Map<Long, Integer> pf = prime.primeFactorize((long)n); for (Iterator<Entry<Long, Integer>> it = pf.entrySet().iterator(); it.hasNext(); ) { Entry<Long, Integer> e = it.next(); long tmp = Math.min(Integer.MAX_VALUE, (long)e.getValue() * k); e.setValue((int)tmp); } Set<Long> hs = new TreeSet<>(); hs.add(1L); for (Entry<Long, Integer> e : pf.entrySet()) { Set<Long> hstmp = new HashSet<>(); long p = e.getKey(); for (int i = 1; i <= e.getValue() && p <= m; i++, p *= e.getKey()) { for (long ee : hs) { if (ee * p <= m) { hstmp.add(ee * p); } else { break; } } } hs.addAll(hstmp); } pr.println(hs.size()); } /** * 素数リスト生成、素数判定、素因数分解などを行う */ static class Prime implements Iterable<Integer> { private int n; private BitSet p; /** * 上限 n までの素数を保持するインスタンスを返す * O(n log log n) * * @param n 保持する素数の上限 */ Prime(int n) { this.n = n; p = new BitSet(n / 2); int m = (int)Math.sqrt(n); // for (int i = 1; i <= m; i++) { for (int bi = p.nextClearBit(0); 2 * (bi + 1) + 1 <= m; bi = p.nextClearBit(bi + 1)) { long i = bi + 1; // if (p.get(i - 1)) { // continue; // } for (long j = 2 * i * (i + 1); 2 * j + 1 <= n; j += 2 * i + 1) { p.set((int)(j - 1)); } } } /** * 素数かどうかを判定する * O(1) * * @param n 判定する値 * @return 素数の場合、true */ boolean isPrime(int n) { if (n == 2) { return true; } if (n == 1 || (n & 0x1) == 0) { return false; } return !p.get(n / 2 - 1); } /** * 素数を含む List を返す * O(pi(n)) (pi(n):nまでの素数の個数) * * @return n 以下の素数を含む List */ List<Integer> getPrimeList() { List<Integer> ret = new ArrayList<>(); for (int p : this) { ret.add(p); } return ret; } /** * 素因数分解の結果を返す * O(pi(n^1/2))? * * @param x 素因数分解をする値 * @return 素因数分解した結果 */ Map<Long, Integer> primeFactorize(long x) { Map<Long, Integer> hm = new TreeMap<>(); long n = x; for (int p : this) { if ((long)p * p > n) { break; } int cnt = 0; while (n % p == 0) { cnt++; n /= p; } if (cnt > 0) { hm.put((long)p, cnt); } } if (n != 1) { hm.put(n, 1); } return hm; } @Override public Iterator<Integer> iterator() { return new PrimeIterator(); } private class PrimeIterator implements Iterator<Integer> { int index; PrimeIterator() { index = -1; } @Override public boolean hasNext() { if (index == -1) { return n >= 2; } else { return 2 * (index + 1) + 1 <= n; } } @Override public Integer next() { if (index == -1) { if (n >= 2) { index = p.nextClearBit(0); return 2; } else { throw new NoSuchElementException(); } } else { int ret = 2 * (index + 1) + 1; if (ret <= n) { index = p.nextClearBit(index + 1); return ret; } else { throw new NoSuchElementException(); } } } } /** * 素数かどうかを判定する(long) * O(n^1/2) * * @param n 判定する値 * @return 素数の場合、true */ static boolean isPrime(long n) { if (n == 2) { return true; } if (n == 1 || (n & 0x1) == 0) { return false; } for (long i = 3; i * i <= n; i += 2) { if (n % i == 0) { return false; } } return true; } } // --------------------------------------------------- public static void main(String[] args) { sc = new Scanner(System.in); pr = new Printer(System.out); solve(); pr.close(); sc.close(); } static class Printer extends PrintWriter { Printer(OutputStream out) { super(out); } } }