#767535 (C#(csc)) No.551 夏休みの思い出（２）

提出ソース

結果

問題	No.551 夏休みの思い出（２）
ユーザー	kuuso1
提出日時	2022-06-02 02:02:50
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	100 ms / 4,000 ms
コード長	6,347 bytes
コンパイル時間	2,744 ms
コンパイル使用メモリ	114,332 KB
実行使用メモリ	28,568 KB
最終ジャッジ日時	2023-10-21 01:04:29
合計ジャッジ時間	7,500 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	29 ms 24,448 KB
testcase_01	AC	28 ms 24,448 KB
testcase_02	AC	28 ms 24,448 KB
testcase_03	AC	31 ms 24,448 KB
testcase_04	AC	32 ms 24,448 KB
testcase_05	AC	42 ms 26,496 KB
testcase_06	AC	39 ms 26,496 KB
testcase_07	AC	30 ms 24,448 KB
testcase_08	AC	29 ms 24,448 KB
testcase_09	AC	29 ms 24,448 KB
testcase_10	AC	29 ms 24,448 KB
testcase_11	AC	28 ms 24,448 KB
testcase_12	AC	27 ms 24,444 KB
testcase_13	AC	28 ms 24,448 KB
testcase_14	AC	30 ms 24,444 KB
testcase_15	AC	30 ms 24,444 KB
testcase_16	AC	29 ms 24,448 KB
testcase_17	AC	29 ms 24,448 KB
testcase_18	AC	30 ms 24,444 KB
testcase_19	AC	29 ms 24,448 KB
testcase_20	AC	28 ms 24,444 KB
testcase_21	AC	28 ms 24,444 KB
testcase_22	AC	29 ms 24,448 KB
testcase_23	AC	29 ms 24,448 KB
testcase_24	AC	28 ms 24,444 KB
testcase_25	AC	29 ms 24,448 KB
testcase_26	AC	28 ms 24,444 KB
testcase_27	AC	71 ms 28,564 KB
testcase_28	AC	58 ms 28,564 KB
testcase_29	AC	66 ms 28,568 KB
testcase_30	AC	85 ms 28,564 KB
testcase_31	AC	56 ms 28,564 KB
testcase_32	AC	86 ms 28,564 KB
testcase_33	AC	61 ms 28,564 KB
testcase_34	AC	68 ms 28,564 KB
testcase_35	AC	57 ms 28,564 KB
testcase_36	AC	60 ms 28,564 KB
testcase_37	AC	62 ms 28,564 KB
testcase_38	AC	75 ms 28,564 KB
testcase_39	AC	59 ms 28,564 KB
testcase_40	AC	60 ms 28,564 KB
testcase_41	AC	100 ms 28,564 KB
testcase_42	AC	61 ms 28,564 KB
testcase_43	AC	62 ms 28,564 KB
testcase_44	AC	66 ms 28,564 KB
testcase_45	AC	63 ms 28,564 KB
testcase_46	AC	71 ms 28,564 KB
testcase_47	AC	30 ms 24,456 KB
testcase_48	AC	28 ms 24,456 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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

ソースコード

raw source code

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace Yukicoder_551 {
	using ModuloCalculation;
	using mlong = ModuloCalculation.mlong;
	class TEST {
		public static void Main() {
			Sol mySol = new Sol();
			mySol.Solve();
		}
	}

	class Sol {
		public void Solve() {
			var sb = new StringBuilder();
			mlong.mod = P;
			for(int t = 0; t < Q; t++) {
				mlong a = A[t], b = B[t], c = C[t];

				var sqrtD = ModSqrt.GetModSqrt(b * b - 4 * a * c);
				if(sqrtD.Length == 0) {
					sb.AppendLine("-1");
				} else if(sqrtD.Length == 1) {
					sb.AppendLine((-b / (2 * a)).ToString());
				} else {
					var alpha = (-b + sqrtD[0]) / (2 * a);
					var beta = (-b + sqrtD[1]) / (2 * a);
					long[] ret = new long[] { (long) alpha, (long) beta };
					Array.Sort(ret);
					sb.AppendLine(String.Join(" ", ret));
				}
			}
			Console.Write(sb.ToString());

		}

		long P, R;
		int Q;
		long[] A, B, C;
		public Sol() {
			var d = rla();
			P = d[0]; R = d[1];
			Q = ri();
			A = new long[Q];
			B = new long[Q];
			C = new long[Q];
			for(int i = 0; i < Q; i++) {
				d = rla();
				A[i] = d[0]; B[i] = d[1]; C[i] = d[2];
			}
		}

		static String rs() { return Console.ReadLine(); }
		static int ri() { return int.Parse(Console.ReadLine()); }
		static long rl() { return long.Parse(Console.ReadLine()); }
		static double rd() { return double.Parse(Console.ReadLine()); }
		static String[] rsa(char sep = ' ') { return Console.ReadLine().Split(sep); }
		static int[] ria(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); }
		static long[] rla(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); }
		static double[] rda(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); }
		static T[] mka<T>(int n, T ini) { T[] ret = new T[n]; for (int i = 0; i < n; i++) ret[i] = ini; return ret; }
		static T[][] mka2<T>(int n, int m, T ini) { T[][] ret = new T[n][]; for (int i = 0; i < n; i++) ret[i] = mka(m, ini); return ret; }
		static T[][][] mka3<T>(int n, int m, int l, T ini) { T[][][] ret = new T[n][][]; for (int i = 0; i < n; i++) ret[i] = mka2(m, l, ini); return ret; }
		static T[][][][] mka4<T>(int n, int m, int l, int k, T ini) { T[][][][] ret = new T[n][][][]; for (int i = 0; i < n; i++) ret[i] = mka3(m, l, k, ini); return ret; }
	}

	namespace ModuloCalculation {
		class ModSqrt {

			public static bool IsQuadraticResidue(mlong v) {
				if (mlong.mod == 2) return true;
				if (v == 0) return true;
				return mlong.ModPow(v, (mlong.mod - 1) / 2) == (mlong)1;
			}
			public static mlong[] GetModSqrt(mlong v) {
				if (!IsQuadraticResidue(v)) return new mlong[0];
				if (mlong.mod == 2) return new mlong[] { v };
				if (v == 0) return new mlong[] { 0 };
				if (v == 1) return new mlong[] { 1, -1 };
				if (mlong.mod % 4 == 3) {
					mlong x = mlong.ModPow(v, (mlong.mod + 1) / 4);
					return new mlong[] { x, -x };
				}

				// Tonelli Shanks
				// https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

				long p = mlong.mod;
				long Q = p - 1;
				int S = 0;
				while (Q % 2 == 0) {
					S++;
					Q >>= 1;
				}

				mlong z = 2;
				while (IsQuadraticResidue(z)) z += 1;

				int M = S;
				mlong c = mlong.ModPow(z, Q);
				mlong t = mlong.ModPow(v, Q);
				mlong R = mlong.ModPow(v, (Q + 1) / 2);

				mlong ret = 0;
				while (true) {
					if (t == 0) { ret = 0; break; }
					if (t == 1) { ret = R; break; }

					int i = 1;
					mlong tt = t * t;
					while (true) {
						if (tt == 1) break;
						tt *= tt;
						i++;
					}

					mlong b = mlong.ModPow(c, (1L << (M - i - 1)));
					M = i;
					c = b * b;
					t = t * c;
					R = R * b;
				}

				return ret * -1 == ret ? new mlong[] { ret } : new mlong[] { ret, -ret };



			}




		}





		struct mlong {

			public static long mod = (long)1e9 + 7;
			long V;

			public mlong(long _v = 0) {
				V = _v;
			}

			public static mlong operator +(mlong a, mlong b) {
				var v0 = a.V + b.V; if (v0 >= mod) v0 -= mod;
				return new mlong(v0);
			}
			public static mlong operator -(mlong a, mlong b) {
				var v0 = mod + a.V - b.V; if (v0 >= mod) v0 -= mod;
				return new mlong(v0);
			}
			public static mlong operator -(mlong b) {
				var v0 = mod - b.V; if (v0 >= mod) v0 -= mod;
				return new mlong(v0);
			}
			public static mlong operator *(mlong a, mlong b) {
				var v0 = a.V * b.V; if (v0 >= mod) v0 %= mod;
				return new mlong(v0);
			}
			public static mlong operator /(mlong a, mlong b) {
				var v0 = a.V * inv(b.V).V; if (v0 >= mod) v0 %= mod;
				return new mlong(v0);
			}


			public static mlong inv(long x) {
				long a = 0, b = 0, c = 0;
				ExtGCD(x, mod, ref a, ref b, ref c);
				return (mlong)((a + mod) % mod);
			}

			public static void ExtGCD(long x, long y, ref long a, ref long b, ref long c) {
				long r0 = x; long r1 = y;
				long a0 = 1; long a1 = 0;
				long b0 = 0; long b1 = 1;
				long q1, r2, a2, b2;
				while (r1 > 0) {
					q1 = r0 / r1;
					r2 = r0 % r1;
					a2 = a0 - q1 * a1;
					b2 = b0 - q1 * b1;
					r0 = r1; r1 = r2;
					a0 = a1; a1 = a2;
					b0 = b1; b1 = b2;
				}
				c = r0;
				a = a0;
				b = b0;
			}

			public static mlong ModPow(mlong a, long k) {
				if (k == 0) return (mlong)1;
				if (a == 0) return (mlong)0;
				mlong x = a;
				mlong ret = 1;
				while (k > 0) {
					if (k % 2 == 1) ret *= x;
					x *= x;
					k >>= 1;
				}
				return ret;
			}


			public static bool operator ==(mlong a, mlong b) {
				return a.Equals(b);
			}
			public static bool operator !=(mlong a, mlong b) {
				return !(a == b);
			}

			public override bool Equals(System.Object obj) {
				if (obj == null) return false;
				mlong p = (mlong)obj;
				if ((System.Object)p == null) return false;
				return p.V == V;
			}
			public override int GetHashCode() {
				return V.GetHashCode();
			}

			public static implicit operator mlong(long n) {
				long v = n % mod; if (v < 0) v += mod;
				return new mlong(v);
			}
			public static implicit operator mlong(int n) {
				long v = n % mod; if (v < 0) v += mod;
				return new mlong(v);
			}
			public static explicit operator long(mlong n) {
				return n.V;
			}

			public override String ToString() {
				return V.ToString();
			}
		}






	}

}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード