結果

問題 No.103 素因数ゲーム リターンズ
コンテスト
ユーザー suikameron1
提出日時 2019-07-05 12:44:02
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 28 ms / 5,000 ms
コード長 2,662 bytes
コンパイル時間 2,430 ms
コンパイル使用メモリ 111,232 KB
実行使用メモリ 27,048 KB
最終ジャッジ日時 2024-09-21 07:59:59
合計ジャッジ時間 2,687 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
static bool[] isPrimes = makePrimeList(100000);//i-1が素数かどうか

	static void Main()
	{
		int n = int.Parse(Console.ReadLine());
    long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
    List<long> grundyList = new List<long>();

    for(int i = 0; i < n; i++)
    {
      List<long> factors = new List<long>();
      factors = Factoring(nums[i]);
      //Console.WriteLine(grundy+" "+i);
      long factorMemo = factors[0];
      long grundy = 1;
      //Console.WriteLine(factors[0]);
      for(int j = 1; j < factors.Count(); j++)
      {
        //Console.WriteLine(factors[j]);
        if(factorMemo == factors[j])
        {
          grundy++;
          grundy %= 3;
        }else
        {
          grundyList.Add(grundy);
          //Console.WriteLine(grundy);
          grundy = 1;
          factorMemo = factors[j];
        }
      }
      grundyList.Add(grundy);
      //Console.WriteLine(grundy+" "+i);
    }

    long[] grundys = new long[grundyList.Count()];
    for(int i = 0; i < grundyList.Count(); i++)
    {
      grundys[i] = grundyList[i];
    }
    if(Nim(grundys) == 0) Console.WriteLine("Bob");
    else Console.WriteLine("Alice");
	}

  static int Nim(long[] grundys)
  {//xorが0か1(0以外)を返す
    int answer = 0;
    int n = grundys.Length;
    long xor = 0;
    for(int i = 0; i < n; i++)
    {
      xor ^= grundys[i];
    }
    if(xor != 0) answer = 1;
    return answer;
  }

  static List<long> Factoring(long originalNum)//引数をO(√n)で素因数分解。リストには同じ数も含む。
  {
    List<long> answers = new List<long>();
    long memo = originalNum;
    for(long i = 2; i <= Math.Sqrt(memo); i++)
    {
      if(!isPrimes[i-1]) continue;//素数でないとき
      else
      {
        while(memo % i == 0)
        {
          memo /= i;
          answers.Add(i);
        }
      }
    }
    if(memo != 1) answers.Add(memo);
    return answers;
  }

  static bool[] makePrimeList(long maxPrime)//「引数1以上」max以下の素数判定。エラトステネスの篩を用いる。
  {
    bool[] isPrimes = new bool[maxPrime];//素数リスト
    isPrimes[0] = false;//1は素数でないのでfalse
    for(long i = 1; i < maxPrime; i++) isPrimes[i] = true;//素数と仮定してtrue
    
    for(long i = 2; i <= Math.Sqrt(maxPrime); i++)
    {
      if(isPrimes[i-1])
      {
        for (long j = i*2; j <= maxPrime; j+=i)
        {
          isPrimes[j-1] = false;//素数でないのでfalse
        }
      }
    }

    return isPrimes;
  }
  
}
0