結果

問題 No.103 素因数ゲーム リターンズ
ユーザー suikameron1suikameron1
提出日時 2019-07-05 11:30:14
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 2,475 bytes
コンパイル時間 948 ms
コンパイル使用メモリ 111,196 KB
実行使用メモリ 27,044 KB
最終ジャッジ日時 2024-09-19 20:09:32
合計ジャッジ時間 2,995 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 25 ms
24,876 KB
testcase_02 AC 25 ms
25,128 KB
testcase_03 AC 26 ms
26,876 KB
testcase_04 AC 24 ms
27,044 KB
testcase_05 WA -
testcase_06 AC 24 ms
24,752 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 24 ms
25,136 KB
testcase_10 WA -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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]);
      long factorMemo = factors[0];
      long grundy = 0;
      for(int j = 1; j < factors.Count(); j++)
      {
        if(factorMemo == factors[j])
        {
          grundy++;
          grundy %= 3;
        }else
        {
          grundyList.Add(grundy);
          grundy = 1;
          factorMemo = factors[i];
        }
      }
      grundyList.Add(grundy);
    }

    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(originalNum); i++)
    {
      if(!isPrimes[i-1]) continue;//素数でないとき
      else
      {
        while(memo % i == 0)
        {
          memo /= i;
          answers.Add(i);
        }
      }
    }
    if(originalNum != 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