結果

問題 No.103 素因数ゲーム リターンズ
ユーザー suikameron1suikameron1
提出日時 2019-07-05 12:44:02
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 27 ms / 5,000 ms
コード長 2,662 bytes
コンパイル時間 2,898 ms
コンパイル使用メモリ 110,124 KB
実行使用メモリ 24,992 KB
最終ジャッジ日時 2023-10-21 06:50:55
合計ジャッジ時間 2,892 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
24,992 KB
testcase_01 AC 24 ms
24,992 KB
testcase_02 AC 25 ms
24,992 KB
testcase_03 AC 25 ms
24,984 KB
testcase_04 AC 24 ms
24,992 KB
testcase_05 AC 24 ms
24,984 KB
testcase_06 AC 25 ms
24,984 KB
testcase_07 AC 25 ms
24,992 KB
testcase_08 AC 24 ms
24,992 KB
testcase_09 AC 26 ms
24,992 KB
testcase_10 AC 24 ms
24,992 KB
testcase_11 AC 24 ms
24,984 KB
testcase_12 AC 25 ms
24,984 KB
testcase_13 AC 26 ms
24,984 KB
testcase_14 AC 25 ms
24,984 KB
testcase_15 AC 25 ms
24,984 KB
testcase_16 AC 24 ms
24,984 KB
testcase_17 AC 24 ms
24,976 KB
testcase_18 AC 24 ms
24,984 KB
testcase_19 AC 25 ms
24,980 KB
testcase_20 AC 27 ms
24,984 KB
testcase_21 AC 25 ms
24,984 KB
testcase_22 AC 24 ms
24,984 KB
testcase_23 AC 24 ms
24,984 KB
testcase_24 AC 25 ms
24,988 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