結果
問題 | No.551 夏休みの思い出(2) |
ユーザー | btk |
提出日時 | 2017-04-05 14:15:36 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,329 ms / 4,000 ms |
コード長 | 6,153 bytes |
コンパイル時間 | 4,489 ms |
コンパイル使用メモリ | 78,908 KB |
実行使用メモリ | 114,204 KB |
最終ジャッジ日時 | 2023-09-22 19:55:59 |
合計ジャッジ時間 | 31,886 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 112 ms
53,704 KB |
testcase_01 | AC | 117 ms
53,736 KB |
testcase_02 | AC | 127 ms
53,788 KB |
testcase_03 | AC | 145 ms
54,232 KB |
testcase_04 | AC | 164 ms
54,152 KB |
testcase_05 | AC | 185 ms
54,252 KB |
testcase_06 | AC | 203 ms
55,932 KB |
testcase_07 | AC | 119 ms
53,768 KB |
testcase_08 | AC | 120 ms
53,688 KB |
testcase_09 | AC | 119 ms
54,028 KB |
testcase_10 | AC | 119 ms
53,636 KB |
testcase_11 | AC | 117 ms
53,780 KB |
testcase_12 | AC | 118 ms
53,636 KB |
testcase_13 | AC | 117 ms
53,384 KB |
testcase_14 | AC | 118 ms
53,580 KB |
testcase_15 | AC | 118 ms
53,636 KB |
testcase_16 | AC | 120 ms
53,776 KB |
testcase_17 | AC | 406 ms
81,888 KB |
testcase_18 | AC | 256 ms
62,828 KB |
testcase_19 | AC | 386 ms
92,204 KB |
testcase_20 | AC | 395 ms
91,992 KB |
testcase_21 | AC | 400 ms
92,184 KB |
testcase_22 | AC | 240 ms
63,284 KB |
testcase_23 | AC | 310 ms
74,240 KB |
testcase_24 | AC | 375 ms
89,932 KB |
testcase_25 | AC | 411 ms
81,688 KB |
testcase_26 | AC | 430 ms
90,072 KB |
testcase_27 | AC | 757 ms
109,824 KB |
testcase_28 | AC | 832 ms
113,772 KB |
testcase_29 | AC | 698 ms
111,320 KB |
testcase_30 | AC | 803 ms
111,588 KB |
testcase_31 | AC | 838 ms
113,636 KB |
testcase_32 | AC | 814 ms
113,868 KB |
testcase_33 | AC | 756 ms
111,592 KB |
testcase_34 | AC | 763 ms
111,856 KB |
testcase_35 | AC | 670 ms
111,316 KB |
testcase_36 | AC | 639 ms
110,940 KB |
testcase_37 | AC | 1,246 ms
113,692 KB |
testcase_38 | AC | 1,238 ms
111,880 KB |
testcase_39 | AC | 971 ms
113,652 KB |
testcase_40 | AC | 1,329 ms
113,836 KB |
testcase_41 | AC | 872 ms
113,900 KB |
testcase_42 | AC | 1,268 ms
113,648 KB |
testcase_43 | AC | 1,022 ms
113,932 KB |
testcase_44 | AC | 1,211 ms
113,796 KB |
testcase_45 | AC | 886 ms
113,856 KB |
testcase_46 | AC | 1,275 ms
114,204 KB |
testcase_47 | AC | 113 ms
53,704 KB |
testcase_48 | AC | 113 ms
53,404 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 = 512345; static final long h = 2123; 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); } }