結果
問題 | No.551 夏休みの思い出(2) |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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-giantll 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);}