結果
| 問題 |
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);
}