結果
問題 |
No.3179 3 time mod
|
ユーザー |
|
提出日時 | 2025-06-14 00:09:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,064 bytes |
コンパイル時間 | 626 ms |
コンパイル使用メモリ | 76,668 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-14 01:44:31 |
合計ジャッジ時間 | 1,944 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 42 |
ソースコード
#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)%pq; if(y<0) y=(y%pq+pq)%pq; __int128 s=((__int128)p*b*x%pq)+pq+(__int128)a*q*y%pq+pq; s=(s%pq+pq)%pq; //x=s mod pq //x=c mod r extgcd(pq, r, x, y); if(x<0) x=(x%pqr+pqr)%pqr; if(y<0) y=(y%pqr+pqr)%pqr; __int128 t=(__int128)pq*c*x%pqr+pqr+(__int128)s*r*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; }