結果

問題 No.551 夏休みの思い出（２）
ユーザー btkbtk
提出日時 2017-04-05 21:15:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,107 ms / 4,000 ms
コード長 2,456 bytes
コンパイル時間 1,585 ms
コンパイル使用メモリ 171,952 KB
実行使用メモリ 127,136 KB
最終ジャッジ日時 2023-09-22 20:22:40
合計ジャッジ時間 56,377 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 4 ms
4,376 KB
testcase_06 AC 4 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 34 ms
8,508 KB
testcase_18 AC 150 ms
18,780 KB
testcase_19 AC 139 ms
18,084 KB
testcase_20 AC 165 ms
18,732 KB
testcase_21 AC 88 ms
13,216 KB
testcase_22 AC 10 ms
5,248 KB
testcase_23 AC 10 ms
5,260 KB
testcase_24 AC 32 ms
8,336 KB
testcase_25 AC 33 ms
8,552 KB
testcase_26 AC 79 ms
12,652 KB
testcase_27 AC 2,587 ms
126,928 KB
testcase_28 AC 2,480 ms
126,980 KB
testcase_29 AC 1,490 ms
80,684 KB
testcase_30 AC 2,385 ms
126,452 KB
testcase_31 AC 2,342 ms
126,904 KB
testcase_32 AC 2,490 ms
126,660 KB
testcase_33 AC 2,504 ms
126,660 KB
testcase_34 AC 2,492 ms
127,012 KB
testcase_35 AC 2,397 ms
126,828 KB
testcase_36 AC 2,472 ms
127,136 KB
testcase_37 AC 2,851 ms
126,976 KB
testcase_38 AC 2,774 ms
126,520 KB
testcase_39 AC 2,501 ms
126,800 KB
testcase_40 AC 2,961 ms
126,928 KB
testcase_41 AC 2,637 ms
126,660 KB
testcase_42 AC 3,107 ms
126,380 KB
testcase_43 AC 2,458 ms
126,672 KB
testcase_44 AC 2,621 ms
126,588 KB
testcase_45 AC 2,503 ms
126,336 KB
testcase_46 AC 2,818 ms
127,120 KB
testcase_47 AC 2 ms
4,376 KB
testcase_48 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
const int H=2523456;
const int h=412;
unordered_map<LL,LL> giant[1024];
void giant_step(LL g,int p){
    LL gg=1;
    REP(i,h)gg=gg*g%p;
    LL ggg=1;
    REP(i,H){
        LL key=ggg;
        LL val=h*i%(p-1);
        LL id=key&1023;
        if(giant[id].count(key)==1)return;
        giant[id][key]=val;
        ggg=ggg*gg%p;
    }
}

LL baby_step(LL key,LL r,int p){
    REP(i,h){
        LL id=key&1023;
        if(giant[id].count(key)){
            LL ah=giant[id][key];
            return (ah-i+p-1)%(p-1);
        }
        key=key*r%p;
    }
    return -1;
}

// a x + b y = gcd(a, b)
// O(log (a+b) )
LL extgcd(LL a, LL b, LL &x, LL &y) {
    LL g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

// mを法とするaの逆元
// O(log a)
LL invMod(LL a,int MOD) {
    LL x, y;
    if (extgcd(a, MOD, x, y) == 1)return (x + MOD) % MOD;
    else return 0; // unsolvable
}
LL pow_mod(LL a,LL n,int MOD){
    LL res=1;
    LL b=1;
    a%=MOD;
    while(n>=b){
        if(n&b)
            res=(res*a)%MOD;
        a=(a*a)%MOD;
        b<<=1;
    }
    return res;
}

LL getX(LL g,int p,LL XX){
    if(XX==0)return 0;
    LL x=baby_step(XX,g,p);
    if(x%2==0)return pow_mod(g,x/2,p);
    else return -1;
}
int main(){
    int P,Q,R;
    cin>>P>>R>>Q;
    giant_step(R,P);
    REP(i,Q){
        LL a,b,c;
        cin>>a>>b>>c;
        LL sq=getX(R,P,(b*b%P+P-4*a*c%P)%P);
        if(sq==-1)cout<<-1<<fin;
        else {
            LL iv=invMod(2*a%P,P);
            LL x=((-b-sq+P+P)%P)*iv%P;
            LL y=((-b+sq+P+P)%P)*iv%P;
            if(x==y)cout<<x<<fin;
            if(x>y)cout<<y<<" "<<x<<fin;
            if(x<y)cout<<x<<" "<<y<<fin;
        }

    }
    return 0;
}
0