結果

問題 No.551 夏休みの思い出（２）
ユーザー makichan
提出日時 2025-01-29 12:59:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,099 bytes
コンパイル時間 6,768 ms
コンパイル使用メモリ 333,992 KB
実行使用メモリ 13,772 KB
最終ジャッジ日時 2025-01-29 13:01:29
合計ジャッジ時間 109,012 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::static_modint<998244353>;
// using mint = atcoder::static_modint<1000000007>;
using namespace std;
using namespace atcoder;
using ld = long double;
using ll = long long;
#define mp(a,b) make_pair(a,b)
#define rep(i,s,n) for(int i=s; i<n; i++)
const vector<int> dx{1,0,-1,0},dy{0,1,0,-1};

ll discrete_log(ll x,ll y,ll mod){
    // x^k=y(mod)を満たす最小のk,無いなら-1を返す

    //yも可逆元
    ll order=mod-1;

    // baby-giant
    ll sq=sqrt(order)+5;
    vector<pair<ll,ll>> list;
    rep(i,0,sq){
        ll c=pow_mod(x,sq*i,mod);
        list.push_back(mp(c,sq*i));
    }
    sort(list.begin(),list.end());
    list.push_back(mp(mod+1,0));//防人

    ll xinv=pow_mod(x,order-1,mod);
    ll Xinvpow=1;

    const ll inf=1e18;
    ll output=inf;
    rep(i,0,sq){
        ll target=y*Xinvpow%mod;
        int id=lower_bound(list.begin(),list.end(),mp(target,0LL))-list.begin();
        if(list[id].first==target){
            ll ans=i+list[id].second;
            output=min(output,ans);
        }
        Xinvpow=Xinvpow*xinv%mod;
    }
    if(output==inf)output=-1;
    return output;
}

void solve(ll p,ll r){
    ll a,b,c;
    cin >> a >> b >> c;
    b*=pow_mod(a,p-2,p);
    b%=p;
    c*=pow_mod(a,p-2,p);
    c%=p;
    ll d=(b*b-4*c+4*p)%p;
    ll k=discrete_log(r,d,p);
    if(d==0){
        b*=pow_mod(2,p-2,p);
        b%=p;
        cout << (p-b)%p << "\n";
    }
    else if(k%2==0){
        ll sqd=pow_mod(r,k/2,p);
        sqd*=pow_mod(2,p-2,p);
        sqd%=p;
        b*=pow_mod(2,p-2,p);
        b%=p;
        if(sqd==0){
            ll ans=(p-b)%p;
            cout << ans << "\n";
        }
        else{
            ll ans[2];
            ans[0]=((p-b)+sqd)%p;
            ans[1]=((p-b)+p-sqd)%p;
            if(ans[0]>ans[1])swap(ans[0],ans[1]);
            cout << ans[0] << " " << ans[1] << "\n";
        }
    }
    else cout << -1 << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll p,r;cin >> p >> r;
    int T;cin >> T;
    rep(i,0,T)solve(p,r);
}
0