結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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);
}
0