結果
| 問題 |
No.551 夏休みの思い出（２）
|
| コンテスト | |
| ユーザー |
 btk
|
| 提出日時 | 2017-04-05 14:05:38 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,787 ms / 4,000 ms |
| コード長 | 6,154 bytes |
| コンパイル時間 | 2,576 ms |
| コンパイル使用メモリ | 85,852 KB |
| 実行使用メモリ | 167,876 KB |
| 最終ジャッジ日時 | 2024-07-08 10:36:36 |
| 合計ジャッジ時間 | 43,292 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 47 |
ソースコード
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 = 1123456;
static final long h = 1123;
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);
}
}