結果

問題 No.7 プライムナンバーゲーム
ユーザー keymoonkeymoon
提出日時 2020-02-05 17:44:23
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 98 ms / 5,000 ms
コード長 2,600 bytes
コンパイル時間 1,143 ms
コンパイル使用メモリ 117,460 KB
実行使用メモリ 27,204 KB
最終ジャッジ日時 2024-04-09 04:48:56
合計ジャッジ時間 2,895 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
24,876 KB
testcase_01 AC 28 ms
26,912 KB
testcase_02 AC 98 ms
27,204 KB
testcase_03 AC 33 ms
24,996 KB
testcase_04 AC 30 ms
24,880 KB
testcase_05 AC 30 ms
25,128 KB
testcase_06 AC 49 ms
24,768 KB
testcase_07 AC 43 ms
24,776 KB
testcase_08 AC 35 ms
22,964 KB
testcase_09 AC 60 ms
25,252 KB
testcase_10 AC 28 ms
25,016 KB
testcase_11 AC 43 ms
26,944 KB
testcase_12 AC 77 ms
24,752 KB
testcase_13 AC 80 ms
26,964 KB
testcase_14 AC 96 ms
24,868 KB
testcase_15 AC 94 ms
26,908 KB
testcase_16 AC 89 ms
25,168 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.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;
using System.Diagnostics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;

static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var primes = Primes(n).ToArray();
        bool[] canWin = new bool[n + 1];
        canWin[0] = true;
        canWin[1] = true;
        for (int i = 2; i < canWin.Length; i++)
        {
            foreach (var item in primes.TakeWhile(x => x <= i))
            {
                if (canWin[i - item]) continue;
                canWin[i] = true;
                break;
            }
        }
        Console.WriteLine(canWin.Last() ? "Win" : "Lose");
    }


    public static IEnumerable<int> Primes(int n)
    {
        if (n < 2) yield break;
        yield return 2;
        ulong[] bitArray = new ulong[(n + 1) / 2 / 64 + 1];

        int[] smallPrimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 };
        foreach (var prime in smallPrimes)
        {
            if (n < prime) yield break;
            yield return prime;

            ulong[] mask = new ulong[prime];
            for (int j = (prime - 3) >> 1; j < (prime << 6); j += prime)
                mask[j >> 6] |= 1UL << j;

            int maskInd = 0;
            for (int i = 0; i < bitArray.Length; i++)
            {
                bitArray[i] |= mask[maskInd];
                if (++maskInd >= prime) maskInd = 0;
            }
        }

        int[] deBruijnIndex = { 0, 1, 59, 2, 60, 40, 54, 3, 61, 32, 49, 41, 55, 19, 35, 4, 62, 52, 30, 33, 50, 12, 14, 42, 56, 16, 27, 20, 36, 23, 44, 5, 63, 58, 39, 53, 31, 48, 18, 34, 51, 29, 11, 13, 15, 26, 22, 43, 57, 38, 47, 17, 28, 10, 25, 21, 37, 46, 9, 24, 45, 8, 7, 6 };
        int maxInd = n / 2;
        for (int i = 0; i < bitArray.Length; i++)
        {
            for (ulong bit = ~bitArray[i]; bit != 0; bit &= bit - 1)
            {
                int index = i << 6 | deBruijnIndex[((bit & (~bit + 1)) * 0x03F566ED27179461UL) >> 58];
                int prime = (index << 1) + 3;
                if (n < prime) yield break;
                yield return prime;
                for (int ind = index; ind <= maxInd; ind += prime)
                    bitArray[ind >> 6] |= 1UL << ind;
            }
        }
    }
}
0