結果
| 問題 |
No.847 Divisors of Power
|
| コンテスト | |
| ユーザー |
 Grenache
|
| 提出日時 | 2019-07-05 22:56:59 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 442 ms / 2,000 ms |
| コード長 | 4,301 bytes |
| コンパイル時間 | 4,007 ms |
| コンパイル使用メモリ | 82,532 KB |
| 実行使用メモリ | 68,408 KB |
| 最終ジャッジ日時 | 2024-10-06 22:50:30 |
| 合計ジャッジ時間 | 9,028 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 26 |
ソースコード
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);
}
}
}