結果

問題 No.551 夏休みの思い出(2)
ユーザー makichan
提出日時 2025-01-29 13:26:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,975 ms / 4,000 ms
コード長 2,158 bytes
コンパイル時間 6,242 ms
コンパイル使用メモリ 333,368 KB
実行使用メモリ 267,384 KB
最終ジャッジ日時 2025-01-29 13:29:39
合計ジャッジ時間 169,900 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

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};
vector<pair<ll,ll>> powlist;
const ll listsize=1e7;
ll p;
ll sq;
ll discrete_log(ll x,ll y,ll mod){
// x^k=y(mod)k,-1
//y
ll order=mod-1;
// baby-giant
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(powlist.begin(),powlist.end(),mp(target,0LL))-powlist.begin();
if(powlist[id].first==target){
ll ans=i+powlist[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 r;cin >> p >> r;
sq=p/listsize+5;
rep(i,0,listsize){
ll c=pow_mod(r,sq*i,p);
powlist.push_back(mp(c,sq*i));
}
sort(powlist.begin(),powlist.end());
powlist.push_back(mp(p+1,0));//
int T;cin >> T;
rep(i,0,T)solve(p,r);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0