結果
問題 | No.1113 二つの整数 / Two Integers |
ユーザー |
![]() |
提出日時 | 2020-07-17 22:15:31 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 29 ms / 1,000 ms |
コード長 | 18,812 bytes |
コンパイル時間 | 1,521 ms |
コンパイル使用メモリ | 126,100 KB |
実行使用メモリ | 26,192 KB |
最終ジャッジ日時 | 2024-11-30 06:35:17 |
合計ジャッジ時間 | 2,536 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.IO;using System.Linq;using System.Text;using System.Runtime.CompilerServices;using System.Runtime.InteropServices;using YukicoderContest257.Extensions;using YukicoderContest257.Numerics;using YukicoderContest257.Questions;namespace YukicoderContest257.Questions{public class QuestionA : AtCoderQuestionBase{public override IEnumerable<object> Solve(TextReader inputStream){var (a, b) = inputStream.ReadValue<long, long>();var gcd = NumericalAlgorithms.Gcd(a, b);for (long i = 2; i * i * i * i <= gcd; i++){var div = i * i;while (gcd % div == 0){gcd /= div;}}var gcdSqrt = (long)Math.Sqrt(gcd);for (int i = 0; i < 3; i++){var div = (gcdSqrt + i) * (gcdSqrt + i);if (gcd % div == 0){gcd /= div;}}yield return gcd > 1 ? "Even" : "Odd";}}}namespace YukicoderContest257{class Program{static void Main(string[] args){IAtCoderQuestion question = new QuestionA();var answers = question.Solve(Console.In);var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };Console.SetOut(writer);foreach (var answer in answers){Console.WriteLine(answer);}Console.Out.Flush();}}}#region Base Classnamespace YukicoderContest257.Questions{public interface IAtCoderQuestion{IEnumerable<object> Solve(string input);IEnumerable<object> Solve(TextReader inputStream);}public abstract class AtCoderQuestionBase : IAtCoderQuestion{public IEnumerable<object> Solve(string input){var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));var reader = new StreamReader(stream, Encoding.Unicode);return Solve(reader);}public abstract IEnumerable<object> Solve(TextReader inputStream);}}#endregion#region Algorithmnamespace YukicoderContest257.Numerics{public static class NumericalAlgorithms{public static long Gcd(long a, long b){if (a < b){(a, b) = (b, a);}var result = b switch{0 => a,long n when n > 0 => Gcd(b, a % b),_ => throw new ArgumentOutOfRangeException($"{nameof(a)}, {nameof(b)}は0以上の整数である必要があります。")};return result;}public static long Lcm(long a, long b){if (a < 0 || b < 0){throw new ArgumentOutOfRangeException($"{nameof(a)}, {nameof(b)}は0以上の整数である必要があります。");}return a / Gcd(a, b) * b;}public static long Factorial(int n){if (n < 0){throw new ArgumentOutOfRangeException(nameof(n), $"{n}は0以上の整数でなければなりません。");}long result = 1;for (int i = 2; i <= n; i++){result *= i;}return result;}public static long Permutation(int n, int r){CheckNR(n, r);long result = 1;for (int i = 0; i < r; i++){result *= n - i;}return result;}public static long Combination(int n, int r){CheckNR(n, r);r = Math.Min(r, n - r);// See https://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinationslong result = 1;for (int i = 1; i <= r; i++){result *= n--;result /= i;}return result;}public static long CombinationWithRepetition(int n, int r) => Combination(n + r - 1, r);public static IEnumerable<(int prime, int count)> PrimeFactorization(int n){if (n <= 1){throw new ArgumentOutOfRangeException(nameof(n), $"{n}は2以上の整数でなければなりません。");}var dictionary = new Dictionary<int, int>();for (int i = 2; i * i <= n; i++){while (n % i == 0){if (dictionary.ContainsKey(i)){dictionary[i]++;}else{dictionary[i] = 1;}n /= i;}}if (n > 1){dictionary[n] = 1;}return dictionary.Select(p => (p.Key, p.Value));}private static void CheckNR(int n, int r){if (n <= 0){throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は正の整数でなければなりません。");}if (r < 0){throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。");}if (n < r){throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。");}}}public readonly struct Modular : IEquatable<Modular>, IComparable<Modular>{private const int DefaultMod = 1000000007;public int Value { get; }public static int Mod { get; set; } = DefaultMod;[MethodImpl(MethodImplOptions.AggressiveInlining)]public Modular(long value){if (unchecked((ulong)value) < unchecked((ulong)Mod)){Value = (int)value;}else{Value = (int)(value % Mod);if (Value < 0){Value += Mod;}}}private Modular(int value) => Value = value;public static Modular Zero => new Modular(0);public static Modular One => new Modular(1);[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Modular operator +(Modular a, Modular b){var result = a.Value + b.Value;if (result >= Mod){result -= Mod; // 剰余演算を避ける}return new Modular(result);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Modular operator -(Modular a, Modular b){var result = a.Value - b.Value;if (result < 0){result += Mod; // 剰余演算を避ける}return new Modular(result);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Modular operator *(Modular a, Modular b) => new Modular((long)a.Value * b.Value);[MethodImpl(MethodImplOptions.AggressiveInlining)]public static Modular operator /(Modular a, Modular b) => a * Pow(b.Value, Mod - 2);// 需要は不明だけど一応public static bool operator ==(Modular left, Modular right) => left.Equals(right);public static bool operator !=(Modular left, Modular right) => !(left == right);public static bool operator <(Modular left, Modular right) => left.CompareTo(right) < 0;public static bool operator <=(Modular left, Modular right) => left.CompareTo(right) <= 0;public static bool operator >(Modular left, Modular right) => left.CompareTo(right) > 0;public static bool operator >=(Modular left, Modular right) => left.CompareTo(right) >= 0;public static implicit operator Modular(long a) => new Modular(a);public static explicit operator int(Modular a) => a.Value;public static explicit operator long(Modular a) => a.Value;public static Modular Pow(int a, int n){switch (n){case 0:return Modular.One;case 1:return a;case int m when m >= 0: // ジャンプテーブル化はできなくなるvar p = Pow(a, m >> 1); // m / 2return p * p * Pow(a, m & 0x01); // m % 2default:throw new ArgumentOutOfRangeException(nameof(n), $"べき指数{nameof(n)}は0以上の整数でなければなりません。");}}private static List<int> _factorialCache;private static List<int> FactorialCache => _factorialCache ??= new List<int>() { 1 };private static int[] FactorialInverseCache { get; set; }const int defaultMaxFactorial = 1000000;public static Modular Factorial(int n){if (n < 0){throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。");}for (int i = FactorialCache.Count; i <= n; i++) // Countが1(0!までキャッシュ済み)のとき1!~n!まで計算{FactorialCache.Add((int)((long)FactorialCache[i - 1] * i % Mod));}return new Modular(FactorialCache[n]);}public static Modular Permutation(int n, int r){CheckNR(n, r);return Factorial(n) / Factorial(n - r);}public static Modular Combination(int n, int r){CheckNR(n, r);r = Math.Min(r, n - r);try{return new Modular(FactorialCache[n]) * new Modular(FactorialInverseCache[r]) * new Modular(FactorialInverseCache[n - r]);}catch (Exception ex) when (ex is NullReferenceException || ex is ArgumentOutOfRangeException){throw new InvalidOperationException($"{nameof(Combination)}を呼び出す前に{nameof(InitializeCombinationTable)}により前計算を行う必要があります。", ex);}}public static void InitializeCombinationTable(int max = defaultMaxFactorial){Factorial(max);FactorialInverseCache = new int[max + 1];var fInv = (Modular.One / Factorial(max)).Value;FactorialInverseCache[max] = fInv;for (int i = max - 1; i >= 0; i--){fInv = (int)((long)fInv * (i + 1) % Mod);FactorialInverseCache[i] = fInv;}}public static Modular CombinationWithRepetition(int n, int r) => Combination(n + r - 1, r);private static void CheckNR(int n, int r){if (n < 0){throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。");}if (r < 0){throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。");}if (n < r){throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。");}}public override string ToString() => Value.ToString();public override bool Equals(object obj) => obj is Modular m ? Equals(m) : false;public bool Equals([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value == other.Value;public int CompareTo([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value.CompareTo(other.Value);public override int GetHashCode() => Value.GetHashCode();}public interface ISemigroup<TSet> where TSet : ISemigroup<TSet>{public TSet Multiply(TSet other);public static TSet operator *(ISemigroup<TSet> a, TSet b) => a.Multiply(b);}public interface IMonoid<TSet> : ISemigroup<TSet> where TSet : IMonoid<TSet>, new(){public TSet Identity { get; }}public interface IGroup<TSet> : IMonoid<TSet> where TSet : IGroup<TSet>, new(){public TSet Invert();public static TSet operator ~(IGroup<TSet> a) => a.Invert();}}#endregion#region Extensionsnamespace YukicoderContest257.Extensions{public static class StringExtensions{public static string Join<T>(this IEnumerable<T> source) => string.Concat(source);public static string Join<T>(this IEnumerable<T> source, char separator) => string.Join(separator, source);public static string Join<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);}public static class TextReaderExtensions{public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));public static string ReadString(this TextReader reader) => reader.ReadLine();public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);// Supports primitive type only.public static T1 ReadValue<T1>(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1));public static (T1, T2) ReadValue<T1, T2>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));return (v1, v2);}public static (T1, T2, T3) ReadValue<T1, T2, T3>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);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 static (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);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 static (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);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 static (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);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 static (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);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 static (T1, T2, T3, T4, T5, T6, T7, T8) ReadValue<T1, T2, T3, T4, T5, T6, T7, T8>(this TextReader reader, char separator = ' '){var inputs = ReadStringArray(reader, separator);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));var v8 = (T8)Convert.ChangeType(inputs[7], typeof(T8));return (v1, v2, v3, v4, v5, v6, v7, v8);}}}#endregion