結果

問題 No.103 素因数ゲーム リターンズ
ユーザー suikameron1suikameron1
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
25,088 KB
testcase_01 AC 26 ms
24,824 KB
testcase_02 AC 25 ms
22,832 KB
testcase_03 AC 26 ms
24,876 KB
testcase_04 AC 26 ms
24,876 KB
testcase_05 AC 26 ms
24,752 KB
testcase_06 AC 27 ms
27,048 KB
testcase_07 AC 26 ms
24,752 KB
testcase_08 AC 26 ms
24,748 KB
testcase_09 AC 26 ms
22,832 KB
testcase_10 AC 27 ms
22,836 KB
testcase_11 AC 25 ms
24,880 KB
testcase_12 AC 26 ms
24,748 KB
testcase_13 AC 26 ms
24,876 KB
testcase_14 AC 28 ms
22,708 KB
testcase_15 AC 26 ms
25,004 KB
testcase_16 AC 27 ms
24,876 KB
testcase_17 AC 27 ms
26,784 KB
testcase_18 AC 26 ms
24,876 KB
testcase_19 AC 27 ms
24,968 KB
testcase_20 AC 28 ms
25,152 KB
testcase_21 AC 28 ms
25,004 KB
testcase_22 AC 26 ms
24,624 KB
testcase_23 AC 27 ms
22,584 KB
testcase_24 AC 28 ms
27,000 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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