結果
問題 | No.551 夏休みの思い出(2) |
ユーザー | kuuso1 |
提出日時 | 2017-01-08 03:58:02 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,366 ms / 4,000 ms |
コード長 | 4,888 bytes |
コンパイル時間 | 995 ms |
コンパイル使用メモリ | 115,892 KB |
実行使用メモリ | 162,496 KB |
最終ジャッジ日時 | 2024-05-09 23:17:55 |
合計ジャッジ時間 | 27,414 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
18,432 KB |
testcase_01 | AC | 31 ms
18,688 KB |
testcase_02 | AC | 32 ms
18,304 KB |
testcase_03 | AC | 34 ms
18,560 KB |
testcase_04 | AC | 36 ms
18,688 KB |
testcase_05 | AC | 41 ms
19,536 KB |
testcase_06 | AC | 42 ms
19,844 KB |
testcase_07 | AC | 31 ms
18,304 KB |
testcase_08 | AC | 32 ms
18,304 KB |
testcase_09 | AC | 31 ms
18,304 KB |
testcase_10 | AC | 32 ms
18,560 KB |
testcase_11 | AC | 32 ms
18,304 KB |
testcase_12 | AC | 31 ms
18,304 KB |
testcase_13 | AC | 33 ms
18,432 KB |
testcase_14 | AC | 32 ms
18,560 KB |
testcase_15 | AC | 31 ms
18,432 KB |
testcase_16 | AC | 32 ms
18,560 KB |
testcase_17 | AC | 49 ms
25,344 KB |
testcase_18 | AC | 84 ms
37,504 KB |
testcase_19 | AC | 83 ms
36,480 KB |
testcase_20 | AC | 88 ms
37,504 KB |
testcase_21 | AC | 108 ms
44,800 KB |
testcase_22 | AC | 36 ms
20,864 KB |
testcase_23 | AC | 43 ms
23,040 KB |
testcase_24 | AC | 67 ms
31,616 KB |
testcase_25 | AC | 48 ms
24,832 KB |
testcase_26 | AC | 65 ms
30,976 KB |
testcase_27 | AC | 1,163 ms
162,192 KB |
testcase_28 | AC | 1,167 ms
162,332 KB |
testcase_29 | AC | 963 ms
162,012 KB |
testcase_30 | AC | 1,150 ms
161,808 KB |
testcase_31 | AC | 936 ms
162,132 KB |
testcase_32 | AC | 1,138 ms
161,936 KB |
testcase_33 | AC | 1,158 ms
162,080 KB |
testcase_34 | AC | 1,118 ms
162,052 KB |
testcase_35 | AC | 996 ms
162,368 KB |
testcase_36 | AC | 1,111 ms
162,300 KB |
testcase_37 | AC | 1,366 ms
161,988 KB |
testcase_38 | AC | 1,291 ms
162,484 KB |
testcase_39 | AC | 1,184 ms
162,232 KB |
testcase_40 | AC | 1,267 ms
162,368 KB |
testcase_41 | AC | 1,184 ms
162,348 KB |
testcase_42 | AC | 1,291 ms
162,496 KB |
testcase_43 | AC | 1,188 ms
162,240 KB |
testcase_44 | AC | 1,212 ms
162,364 KB |
testcase_45 | AC | 1,188 ms
162,108 KB |
testcase_46 | AC | 1,324 ms
162,304 KB |
testcase_47 | AC | 32 ms
18,432 KB |
testcase_48 | AC | 32 ms
18,048 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.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using System.Diagnostics; using System.Diagnostics.Contracts; using CT = System.Diagnostics.Contracts.Contract; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ // O( W + Q*(H+log(mod)) ) where mod / W = H, W:Initialize of BabyStep, H: Giant Step query; StringBuilder sb = new StringBuilder(); long W = (int) 5e6; long H = mod / W + 1; DiscreteLog.Init(mod, primRoot, W); long Inv2 = ModInv(2,mod); for(int i=0;i<Q;i++){ long a = 1; long b = B[i] * ModInv(A[i],mod) % mod; long c = C[i] * ModInv(A[i],mod) % mod; long D = ((b * b) % mod +mod - ((4 * a * c) % mod) ) % mod; if(D == 0){ // multiple root case: long sol = (mod - b) * Inv2 % mod; sb.AppendLine(sol.ToString()); continue; } long idx = DiscreteLog.Calc(D); if(idx % 2 != 0){ // no SquareRoot for D; sb.AppendLine("-1"); continue; }else{ long sqrt = ModPow(primRoot,idx/2,mod); long[] sols = new long[]{ ( ( mod - b + sqrt ) % mod ) * Inv2 % mod, ( ( mod - b + mod - sqrt) % mod ) * Inv2 % mod }; Array.Sort(sols); sb.AppendLine(String.Format("{0} {1}",sols[0],sols[1])); } } Console.Write(sb.ToString()); } int Q; long[] A,B,C; static long mod; long primRoot; public Sol(){ // input read var d = rla(); mod = d[0]; primRoot = 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 bool isPrimitiveRoot(long x, long mod){ if( x == 0 || x == 1 ) return false; long w = (long)1e5; long h = mod / w; Dictionary<long,long> D = new Dictionary<long,long>((int)w+1); long xx = 1; for(long j=0;j<w;j++){ if(D.ContainsKey(xx)){ if(j >= mod - 1){ return true; }else{ return false; } } D.Add(xx,j); xx *= x; xx %= mod; } long nxx = ModInv(xx,mod); long yy = nxx; for(long i=1;i<h+1;i++){ if(D.ContainsKey(yy)){ long idx = w * i + D[yy]; if(idx >= mod - 1){ return true; }else{ return false; } } yy *= nxx; yy %= mod; } return true; } static long ModInv(long x, long mod){ long a = 0, b = 0, c = 0; if(x == 0) return 0; ExtGCD(x, mod, ref a, ref b, ref c); if(c != 1)return 0; return (a + mod) % mod; } 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; } static long ModPow(long x,long k,long mod){ if(k == 0)return 1; if(x == 0)return 0; long ret = 1; long xx = x; while(k>0){ if((k&1)==1){ret *= xx; if(ret >= mod) ret %= mod;} xx *= xx; if(xx >= mod) xx %= mod; k>>=1; } return ret; } 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));} } class DiscreteLog{ static long mod; static long primRoot; static long WInvPrimRoot; // Pow(primRoot , -W) static long W,H; static Dictionary<long,long> WTable; public static void Init(long mod_, long primRoot_, long w){ mod = mod_; primRoot = primRoot_; W = w; H = mod / w + 1; WTable = new Dictionary<long,long>((int)W+20); long xx = 1; for(long j=0;j<w;j++){ if(WTable.ContainsKey(xx))break; WTable.Add(xx,j); xx *= primRoot; xx %= mod; } WInvPrimRoot = ModInv(xx,mod); } public static long Calc(long x){ long nxx = WInvPrimRoot; long yy = x; for(long i=0;i<H;i++){ if(WTable.ContainsKey(yy)){ return W * i + WTable[yy]; } yy *= nxx; yy %= mod; } return 0; } static long ModInv(long x,long mod){ return ModPow(x, mod - 2, mod); } static long ModPow(long x,long k,long mod){ if(k == 0)return 1; if(x == 0)return 0; long ret = 1; long xx = x; while(k>0){ if((k&1)==1){ret *= xx; if(ret >= mod) ret %= mod;} xx *= xx; if(xx >= mod) xx %= mod; k>>=1; } return ret; } }