結果
問題 | No.2 素因数ゲーム |
ユーザー | fairy_lettuce |
提出日時 | 2020-09-19 01:36:17 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 36 ms / 5,000 ms |
コード長 | 11,882 bytes |
コンパイル時間 | 2,948 ms |
コンパイル使用メモリ | 121,572 KB |
実行使用メモリ | 28,112 KB |
最終ジャッジ日時 | 2024-06-22 16:01:01 |
合計ジャッジ時間 | 4,768 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
25,684 KB |
testcase_01 | AC | 29 ms
25,840 KB |
testcase_02 | AC | 30 ms
25,940 KB |
testcase_03 | AC | 34 ms
27,884 KB |
testcase_04 | AC | 33 ms
27,524 KB |
testcase_05 | AC | 33 ms
28,008 KB |
testcase_06 | AC | 33 ms
25,776 KB |
testcase_07 | AC | 34 ms
27,888 KB |
testcase_08 | AC | 31 ms
25,844 KB |
testcase_09 | AC | 32 ms
25,988 KB |
testcase_10 | AC | 32 ms
28,004 KB |
testcase_11 | AC | 33 ms
26,032 KB |
testcase_12 | AC | 36 ms
25,716 KB |
testcase_13 | AC | 32 ms
27,964 KB |
testcase_14 | AC | 32 ms
25,972 KB |
testcase_15 | AC | 31 ms
28,012 KB |
testcase_16 | AC | 31 ms
25,964 KB |
testcase_17 | AC | 31 ms
25,968 KB |
testcase_18 | AC | 31 ms
25,848 KB |
testcase_19 | AC | 28 ms
26,164 KB |
testcase_20 | AC | 29 ms
25,940 KB |
testcase_21 | AC | 29 ms
28,112 KB |
testcase_22 | AC | 34 ms
23,676 KB |
testcase_23 | AC | 31 ms
25,972 KB |
testcase_24 | AC | 31 ms
27,788 KB |
testcase_25 | AC | 32 ms
28,036 KB |
testcase_26 | AC | 32 ms
26,228 KB |
testcase_27 | AC | 32 ms
28,104 KB |
testcase_28 | AC | 33 ms
26,028 KB |
testcase_29 | AC | 34 ms
25,972 KB |
testcase_30 | AC | 32 ms
24,112 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Collections.Generic; using System.Linq; using System.Numerics; using System.Runtime.CompilerServices; namespace FertiLib.Contest.A { static class Program { public static void Solve(Scanner cin) { long n = cin.ReadLong(); var prime = Factorizer.Factorize(n); var xor = 0L; foreach (var e in prime) { xor ^= e.Value; } if (xor != 0) Console.WriteLine("Alice"); else Console.WriteLine("Bob"); } public static void Main(string[] args) { var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw); var cin = new Scanner(); Solve(cin); Console.Out.Flush(); } public static void YESNO(bool condition) => Console.WriteLine(condition ? "YES" : "NO"); public static void YesNo(bool condition) => Console.WriteLine(condition ? "Yes" : "No"); public static void yesno(bool condition) => Console.WriteLine(condition ? "yes" : "no"); public static bool Chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) >= 0) return false; a = b; return true; } public static bool Chmin<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) <= 0) return false; a = b; return true; } } public static class Factorizer { // http://miller-rabin.appspot.com/ static readonly long[] baseSingle = { 126401071349994536 }; // <= 291,831 static readonly long[] baseDouble = { 336781006125, 9639812373923155 }; // <= 1,050,535,501 static readonly long[] baseQuad = { 2, 2570940, 211991001, 3749873356 }; // <= 47,636,622,961,201 static readonly long[] baseBig = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }; /// <summary> /// Factorizes n. /// </summary> /// <param name="n">The number to factorize.</param> /// <returns>Dictionary that has prime factors in Key, the number of each factor in Value.</returns> public static SortedDictionary<long, int> Factorize(long n) { var ret = new SortedDictionary<long, int>(); var que = new Queue<long>(); que.Enqueue(n); while (que.Count > 0) { var now = que.Dequeue(); if (now == 1) continue; if (IsPrime(now)) { if (ret.ContainsKey(now)) ret[now]++; else ret.Add(now, 1); continue; } long f = FindFactor(now); que.Enqueue(f); que.Enqueue(now / f); } return ret; } /// <summary> /// Tests if n is prime or not using Miller-Rabin Algorithm. Complexity: O(log^2 n) /// </summary> /// <param name="n">The number to test.</param> /// <returns>True if prime, False otherwise.</returns> public static bool IsPrime(long n) { if (n == 1) return false; if (n == 2) return true; long d = n - 1; int s = 0; while (d % 2 == 0) { d /= 2; s++; } long[] bases; if (n < 291831) bases = baseSingle; else if (n < 1050535501) bases = baseDouble; else if (n < 47636622961201) bases = baseQuad; else bases = baseBig; foreach (var e in bases) { if (!MillerRabinTest(e, d, n, s)) return false; } return true; } private static bool MillerRabinTest(long e, long d, long n, long s) { long pow = ModPow(e, d, n); if (pow == 1) return true; for (int i = 0; i < s; i++) { if (pow == n - 1) return true; pow = ModPow(pow, 2, n); } return false; } private static long ModPow(long a, long p, long mod) { if (mod <= int.MaxValue) { a %= mod; long ret = 1; for (long i = 1; i <= p; i *= 2) { if (p / i % 2 == 1) { ret *= a; ret %= mod; } a *= a; a %= mod; } return ret; } else { BigInteger retbig = 1; BigInteger abig = a % mod; for (BigInteger i = 1; i <= p; i *= 2) { if (p / i % 2 == 1) { retbig *= abig; retbig %= mod; } abig *= abig; abig %= mod; } return (long)retbig; } } /// <summary> /// Finds a factor of n by Pollard's ρ algorithm. Complexity: O(n^(1/4)) /// </summary> /// <param name="n">The number to get a factor.</param> /// <returns>A prime factor of n.</returns> public static long FindFactor(long n) { if (n % 2 == 0) return 2; long i = 0; while (true) { i++; long x = i; long y = Next(i, n); while (true) { long g = GCD(x - y, n); if (g >= n) break; if (1 < g) return g; x = Next(x, n); y = Next(y, n); y = Next(y, n); } } } private static long Next(long x, long mod) { BigInteger tmp = x; tmp *= tmp; tmp++; tmp %= mod; return (long)tmp; } private static long GCD(long a, long b) { a = Math.Abs(a); b = Math.Abs(b); while (a > 0) { b %= a; var x = a; a = b; b = x; } return b; } } static class Extention { public static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x); public static int UpperBound<T>(this IList<T> list, T value) => list.BinarySearch(value, true, 0, list.Count, Comparer<T>.Default); public static int LowerBound<T>(this IList<T> list, T value) => list.BinarySearch(value, false, 0, list.Count, Comparer<T>.Default); public static int BinarySearch<T>(this IList<T> list, T value, bool isUpperBound, int index, int length, Comparer<T> comparer) { var ng = index - 1; var ok = index + length; while (ok - ng > 1) { var mid = ng + (ok - ng) / 2; var res = comparer.Compare(list[mid], value); if (res < 0 || (isUpperBound && res == 0)) ng = mid; else ok = mid; } return ok; } } class Scanner { string[] s; int i; char[] separator = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string Read() => ReadString(); public string ReadString() { if (i < s.Length) return s[i++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); s = st.Split(separator, StringSplitOptions.RemoveEmptyEntries); if (s.Length == 0) return ReadString(); i = 0; return s[i++]; } public string[] ReadStringArray(int N) { string[] Array = new string[N]; for (int i = 0; i < N; i++) { Array[i] = ReadString(); } return Array; } public int ReadInt() { return int.Parse(ReadString()); } public int[] ReadIntArray(int N, int add = 0) { int[] Array = new int[N]; for (int i = 0; i < N; i++) { Array[i] = ReadInt() + add; } return Array; } public long ReadLong() { return long.Parse(ReadString()); } public long[] ReadLongArray(int N, long add = 0) { long[] Array = new long[N]; for (int i = 0; i < N; i++) { Array[i] = ReadLong() + add; } return Array; } public double ReadDouble() { return double.Parse(ReadString()); } public double[] ReadDoubleArray(int N, double add = 0) { double[] Array = new double[N]; for (int i = 0; i < N; i++) { Array[i] = ReadDouble() + add; } return Array; } public T1 ReadValue<T1>() => (T1)Convert.ChangeType(ReadString(), typeof(T1)); public (T1, T2) ReadValue<T1, T2>() { var inputs = ReadStringArray(2); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); return (v1, v2); } public (T1, T2, T3) ReadValue<T1, T2, T3>() { var inputs = ReadStringArray(3); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); return (v1, v2, v3); } public (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>() { var inputs = ReadStringArray(4); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); return (v1, v2, v3, v4); } public (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>() { var inputs = ReadStringArray(5); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); return (v1, v2, v3, v4, v5); } public (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>() { var inputs = ReadStringArray(6); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); return (v1, v2, v3, v4, v5, v6); } public (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>() { var inputs = ReadStringArray(7); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7)); return (v1, v2, v3, v4, v5, v6, v7); } public T1[] ReadValueArray<T1>(int N) { var v1 = new T1[N]; for (int i = 0; i < N; i++) { v1[i] = ReadValue<T1>(); } return v1; } public (T1[], T2[]) ReadValueArray<T1, T2>(int N) { var (v1, v2) = (new T1[N], new T2[N]); for (int i = 0; i < N; i++) { var (t1, t2) = ReadValue<T1, T2>(); v1[i] = t1; v2[i] = t2; } return (v1, v2); } public (T1[], T2[], T3[]) ReadValueArray<T1, T2, T3>(int N) { var (v1, v2, v3) = (new T1[N], new T2[N], new T3[N]); for (int i = 0; i < N; i++) { var (t1, t2, t3) = ReadValue<T1, T2, T3>(); v1[i] = t1; v2[i] = t2; v3[i] = t3; } return (v1, v2, v3); } public (T1[], T2[], T3[], T4[]) ReadValueArray<T1, T2, T3, T4>(int N) { var (v1, v2, v3, v4) = (new T1[N], new T2[N], new T3[N], new T4[N]); for (int i = 0; i < N; i++) { var (t1, t2, t3, t4) = ReadValue<T1, T2, T3, T4>(); v1[i] = t1; v2[i] = t2; v3[i] = t3; v4[i] = t4; } return (v1, v2, v3, v4); } public (T1[], T2[], T3[], T4[], T5[]) ReadValueArray<T1, T2, T3, T4, T5>(int N) { var (v1, v2, v3, v4, v5) = (new T1[N], new T2[N], new T3[N], new T4[N], new T5[N]); for (int i = 0; i < N; i++) { var (t1, t2, t3, t4, t5) = ReadValue<T1, T2, T3, T4, T5>(); v1[i] = t1; v2[i] = t2; v3[i] = t3; v4[i] = t4; v5[i] = t5; } return (v1, v2, v3, v4, v5); } public (T1[], T2[], T3[], T4[], T5[], T6[]) ReadValueArray<T1, T2, T3, T4, T5, T6>(int N) { var (v1, v2, v3, v4, v5, v6) = (new T1[N], new T2[N], new T3[N], new T4[N], new T5[N], new T6[N]); for (int i = 0; i < N; i++) { var (t1, t2, t3, t4, t5, t6) = ReadValue<T1, T2, T3, T4, T5, T6>(); v1[i] = t1; v2[i] = t2; v3[i] = t3; v4[i] = t4; v5[i] = t5; v6[i] = t6; } return (v1, v2, v3, v4, v5, v6); } public (T1[], T2[], T3[], T4[], T5[], T6[], T7[]) ReadValueArray<T1, T2, T3, T4, T5, T6, T7>(int N) { var (v1, v2, v3, v4, v5, v6, v7) = (new T1[N], new T2[N], new T3[N], new T4[N], new T5[N], new T6[N], new T7[N]); for (int i = 0; i < N; i++) { var (t1, t2, t3, t4, t5, t6, t7) = ReadValue<T1, T2, T3, T4, T5, T6, T7>(); v1[i] = t1; v2[i] = t2; v3[i] = t3; v4[i] = t4; v5[i] = t5; v6[i] = t6; v7[i] = t7; } return (v1, v2, v3, v4, v5, v6, v7); } } }