結果
問題 | No.551 夏休みの思い出(2) |
ユーザー | btk |
提出日時 | 2017-04-05 14:17:55 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,597 ms / 4,000 ms |
コード長 | 6,153 bytes |
コンパイル時間 | 2,439 ms |
コンパイル使用メモリ | 85,804 KB |
実行使用メモリ | 93,324 KB |
最終ジャッジ日時 | 2023-09-22 19:58:15 |
合計ジャッジ時間 | 28,225 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 110 ms
53,536 KB |
testcase_01 | AC | 113 ms
54,072 KB |
testcase_02 | AC | 123 ms
51,612 KB |
testcase_03 | AC | 138 ms
54,180 KB |
testcase_04 | AC | 161 ms
54,332 KB |
testcase_05 | AC | 192 ms
54,048 KB |
testcase_06 | AC | 193 ms
54,004 KB |
testcase_07 | AC | 118 ms
53,424 KB |
testcase_08 | AC | 112 ms
54,028 KB |
testcase_09 | AC | 117 ms
53,848 KB |
testcase_10 | AC | 116 ms
53,824 KB |
testcase_11 | AC | 114 ms
53,760 KB |
testcase_12 | AC | 113 ms
53,860 KB |
testcase_13 | AC | 112 ms
53,740 KB |
testcase_14 | AC | 111 ms
53,684 KB |
testcase_15 | AC | 115 ms
53,848 KB |
testcase_16 | AC | 117 ms
53,892 KB |
testcase_17 | AC | 280 ms
77,184 KB |
testcase_18 | AC | 268 ms
77,084 KB |
testcase_19 | AC | 332 ms
77,304 KB |
testcase_20 | AC | 274 ms
77,056 KB |
testcase_21 | AC | 275 ms
77,048 KB |
testcase_22 | AC | 192 ms
58,736 KB |
testcase_23 | AC | 275 ms
69,572 KB |
testcase_24 | AC | 299 ms
69,736 KB |
testcase_25 | AC | 179 ms
56,424 KB |
testcase_26 | AC | 274 ms
77,372 KB |
testcase_27 | AC | 706 ms
93,068 KB |
testcase_28 | AC | 680 ms
93,324 KB |
testcase_29 | AC | 519 ms
83,632 KB |
testcase_30 | AC | 628 ms
92,916 KB |
testcase_31 | AC | 509 ms
83,320 KB |
testcase_32 | AC | 647 ms
93,044 KB |
testcase_33 | AC | 1,496 ms
92,532 KB |
testcase_34 | AC | 644 ms
86,864 KB |
testcase_35 | AC | 528 ms
83,848 KB |
testcase_36 | AC | 621 ms
84,188 KB |
testcase_37 | AC | 1,597 ms
92,800 KB |
testcase_38 | AC | 1,280 ms
92,876 KB |
testcase_39 | AC | 1,001 ms
92,816 KB |
testcase_40 | AC | 1,167 ms
92,800 KB |
testcase_41 | AC | 795 ms
92,804 KB |
testcase_42 | AC | 1,532 ms
93,088 KB |
testcase_43 | AC | 747 ms
93,180 KB |
testcase_44 | AC | 1,076 ms
92,904 KB |
testcase_45 | AC | 1,283 ms
92,868 KB |
testcase_46 | AC | 1,326 ms
92,656 KB |
testcase_47 | AC | 108 ms
54,200 KB |
testcase_48 | AC | 110 ms
53,652 KB |
ソースコード
import java.io.*; import java.math.BigInteger; import java.util.*; /** * Created by btk on 2017/03/16. */ public class Main { static FastScanner in; static PrintWriter out; static final long H = 312345; static final long h = 3423; static HashMap<Integer,Integer> getGiantStep(long r,int p){ HashMap<Integer,Integer> ret=new HashMap<Integer,Integer>(); long g = 1; for (int i = 0; i < h; i++) { g=g*r%p; } long gg=1; for (int i = 0; i < H; i++) { Integer key=Integer.valueOf((int)gg); Integer val=Integer.valueOf((int)(h*i%(p-1))); ret.put(key,val); gg=gg*g%p; } return ret; } static int getBabyStep(long y,long r,int p,HashMap<Integer,Integer> giant){ for (int i = 0; i < h; i++) { Integer key = Integer.valueOf((int)y); if(giant.containsKey(key)){ long ah = giant.get(key).longValue(); return (int)((ah-i+p-1)%(p-1)); } y = y *r %p; } return -1; } static int getG(int p){ for (int r = 2; r < p ; r++) { int[] memo = new int[p]; for (int i = 0; i < p; i++) { memo[i] = 0; } boolean ans = true; long k = 1; for (int i = 0; i < p - 1; i++) { if (memo[(int)k] == 1) ans = false; memo[(int)k] = 1; k = k * r % p; } if (ans) return r; } return -1; } static long powmod(long a,long n,long p){ long ret=1; a%=p; while(n>0){ if((n&1)==1) ret=ret*a%p; a=a*a%p; n>>=1; } return ret; } static long getX(long g,int p,long XX,HashMap<Integer,Integer> giant){ if(XX==0)return 0; int x=getBabyStep(XX,g,p,giant); if(x%2==0)x/=2; else return -1; return powmod(g,x,p); } // a x + b y = gcd(a, b) // O(log (a+b) ) static long extgcd(long a, long b, long[] x, long[] y) { long g = a; x[0] = 1; y[0] = 0; if (b != 0) { g = extgcd(b, a % b, y, x); y[0] -= (a / b) * x[0]; } return g; } // mを法とするaの逆元 // O(log a) static long invMod(long a,int MOD) { long[] x=new long[1], y=new long[1]; if (extgcd(a, MOD, x, y) == 1)return (x[0] + MOD) % MOD; else return 0; // unsolvable } static void solve() { int P = in.nextInt(); long R = in.nextLong(); int Q = in.nextInt(); HashMap<Integer,Integer> giant=getGiantStep(R,P); for (int q = 0; q < Q; q++) { long a=in.nextInt(); long b=in.nextInt(); long c=in.nextInt(); long sqrt=getX(R,P,(b*b%P+P-4*a*c%P)%P,giant); if(sqrt==-1)out.println(-1); else{ long x = ((P+P-b-sqrt)%P)*invMod(2*a%P,P)%P; long y = ((P+P-b+sqrt)%P)*invMod(2*a%P,P)%P; if(x==y)out.println(x); if(x>y)out.println(y+" "+x); if(x<y)out.println(x+" "+y); } } } public static void main(String[] args){ in = new FastScanner(); out = new PrintWriter(System.out); solve(); out.flush(); out.close(); } } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next());} } class Pair implements Comparable<Pair> { BigInteger a; int b; public Pair(BigInteger a, int b) { this.a = a; this.b = b; } //(a,b)が一致 @Override public boolean equals(Object o) { if (o instanceof Pair) { Pair p = (Pair) o; return a == p.a && b == p.b; } return super.equals(o); } //辞書順比較 @Override public int compareTo(Pair o) { if (!a.equals(o.a)) { return a.compareTo(o.a); } return Integer.compare(b,o.b); } }