結果
| 問題 |
No.551 夏休みの思い出（２）
|
| コンテスト | |
| ユーザー |
 kuuso1
|
| 提出日時 | 2022-06-02 02:02:50 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 110 ms / 4,000 ms |
| コード長 | 6,347 bytes |
| コンパイル時間 | 1,354 ms |
| コンパイル使用メモリ | 115,748 KB |
| 実行使用メモリ | 30,680 KB |
| 最終ジャッジ日時 | 2024-09-21 01:54:18 |
| 合計ジャッジ時間 | 6,029 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 47 |
コンパイルメッセージ
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;
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();
}
}
}
}