結果
問題 |
No.129 お年玉(2)
|
ユーザー |
|
提出日時 | 2025-09-26 22:03:50 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 1,013 bytes |
コンパイル時間 | 5,518 ms |
コンパイル使用メモリ | 163,600 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-09-26 22:03:58 |
合計ジャッジ時間 | 4,086 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
module main; // http://rsujskf.s602.xrea.com/?yukicoder_129 より // 組み合わせ、素因数分解、剰余 import std; immutable MOD = 10L ^^ 9; // エラトステネスの篩によってm以上n未満の素数の表を返す T[] sieve(T)(T m, T n) { T[] primes = new T[](n); foreach (i; 2 .. n) primes[i] = i; for (T i = 2; i*i < n; ++i) if (primes[i]) for (T j = i*i; j < n; j += i) primes[j] = 0; return primes.remove!(a => a < m).array; } void main() { // 入力 auto N = readln.chomp.to!long; auto M = readln.chomp.to!long; // 答えの計算 auto primes = sieve(2L, 10_000L); N /= 1000; N %= M; N = min(N, M - N); auto up = iota(M, M - N, -1).array; long ans = 1; foreach (p; primes) { long i = p; long num = 0, x = N; while (x) { x /= i; num += x; } if (!num) break; foreach (j; 0 .. N) { while (num > 0 && up[j] % i == 0) { up[j] /= i; num--; } } } foreach (u; up) { ans = (ans * u) % MOD; } // 答えの出力 writeln(ans); }