結果
問題 | No.28 末尾最適化 |
ユーザー | nebukuro09 |
提出日時 | 2017-06-01 11:32:31 |
言語 | D (dmd 2.107.1) |
結果 |
AC
|
実行時間 | 435 ms / 5,000 ms |
コード長 | 1,072 bytes |
コンパイル時間 | 894 ms |
コンパイル使用メモリ | 109,408 KB |
実行使用メモリ | 6,720 KB |
最終ジャッジ日時 | 2023-09-03 13:48:37 |
合計ジャッジ時間 | 1,805 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 435 ms
6,720 KB |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; immutable long MOD = 100000009; long[] primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]; void solve() { auto s = readln.split.map!(to!long); auto seed = s[0]; auto N = s[1].to!int; auto K = s[2].to!int; auto B = s[3]; auto A = new long[](N+1); A[0] = seed; foreach (i; 0..N) { A[i+1] = 1 + ((A[i] * A[i] % MOD + A[i] * 12345 % MOD)) % MOD; } long ans = 1 << 29; foreach (p; primes) { if (B % p != 0) continue; auto cnt = new long[](N+1); fill(cnt, 0); foreach (i; 0..N+1) { long a = A[i]; while (a % p == 0) cnt[i]++, a/=p; } cnt.sort(); long b = B; long d = 0; while (b % p == 0) d++, b/=p; ans = min(ans, cnt[0..K].sum / d); } ans.writeln; } void main() { auto Q = readln.chomp.to!int; while (Q--) solve; }