結果
問題 |
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 |
ソースコード
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"); }