結果

問題 No.103 素因数ゲーム リターンズ
コンテスト
ユーザー ゴリポン先生
提出日時 2025-08-24 11:30:39
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 972 bytes
コンパイル時間 4,217 ms
コンパイル使用メモリ 166,920 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-24 11:30:44
合計ジャッジ時間 3,203 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://mmxsrup.hatenablog.com/entry/2016/09/14/101621 より
// Grundy数、素因数分解、Nim
import std;

// xを素因数分解して[素因数、指数]の配列を返す
Tuple!(T, int)[] factorize(T)(T x)
{
	typeof(return) res;

	void addFactor(T n)
	{
		auto f = tuple(n, 0);
		while (x % n == 0) {
			x /= n;
			++f[1];
		}
		if (f[1]) res ~= f;
	}

	addFactor(2);	// まず2で割る
	for (T d = 3; d * d <= x; d += 2) {	// 3以上の奇数で割っていく
		addFactor(d);
	}
	if (x > 1) res ~= tuple(x, 1);	// ここまで残っているxは素数のはず

	return res;
}

void main()
{
	// 入力
	int N = readln.chomp.to!int;
	auto M = readln.split.to!(int[]);
	// 答えの計算
	int sum = 0;
	foreach (m; M) {
		foreach (f; factorize(m)) {
			// 一度に取り除けるのは2つまでなので、3で割った余りをとる
			sum ^= f[1] % 3;
		}
	}
	// 答えの出力
	if (sum == 0)
		writeln("Bob");
	else
		writeln("Alice");
}
0