結果
問題 |
No.3179 3 time mod
|
ユーザー |
|
提出日時 | 2025-06-13 23:17:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,032 bytes |
コンパイル時間 | 727 ms |
コンパイル使用メモリ | 75,872 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-06-13 23:17:46 |
合計ジャッジ時間 | 2,422 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 WA * 14 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; ll extgcd(ll a, ll b, ll& x, ll& y){ if(b==0){ x=1, y=0; return a; } ll x1, y1; ll gcd=extgcd(b, a%b, x1, y1); x=y1; y=x1-(a/b)*y1; return gcd; } int main(void){ ll n; cin >> n; ll p, q, r, a, b, c; cin >> p >> q >> r >> a >> b >> c; ll x, y; ll pq=p*q, pqr=p*q*r; extgcd(p, q, x, y); //px+qy=1 //px=1 mod q //qy=1 mod p //if(x<0) x=(x+pq)%pq; //if(y<0) y=(y+pq)%pq; ll s=(p*b*x%pq)+pq+(a*q*y)%pq+pq; s%=pq; //x=s mod pq //x=c mod r extgcd(pq, r, x, y); //if(x<0) x=(x+pqr)%pqr; //if(y<0) y=(y+pqr)%pqr; ll t=(pq*c)%pqr*x%pqr+pqr+s*r%pqr*y%pqr+pqr; t%=pqr; //cout << pqr << ' ' << t << endl; if(t>n){ cout << 0 << endl; return 0; } //cout << -11%3 << endl; ll left=0, right=2e18/pqr; while(right-left>1){ ll mid=(left+right)/2; ll now=mid*pqr+t; if(now<=n) left=mid; else right=mid; } cout << right << endl; //意味わからん return 0; }