#356648 (C#(csc)) No.103 素因数ゲーム リターンズ

• 問題: No.103 素因数ゲーム リターンズ
• ユーザー: suikameron1
• 提出日時: 2019-07-05 11:38:39
• 言語: C#(csc) (csc 3.9.0)
• 結果: WA
• 実行時間: -
• コード長: 2,622 bytes
• コンパイル時間: 774 ms
• コンパイル使用メモリ: 113,376 KB
• 実行使用メモリ: 26,880 KB
• 最終ジャッジ日時: 2024-09-19 20:09:56
• 合計ジャッジ時間: 2,089 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 4 WA * 1
other	AC * 6 RE * 14

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
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 = 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[i];
        }
      }
      grundyList.Add(grundy);
      //Console.WriteLine(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(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;
  }
  
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX