結果

問題 No.3179 3 time mod
コンテスト
ユーザー Rumain831
提出日時 2026-08-25 07:58:29
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1 ms / 2,000 ms
+ 463µs
コード長 1,615 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,175 ms
コンパイル使用メモリ 174,680 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-08-25 07:58:40
合計ジャッジ時間 3,912 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}

//ax≡b mod m (0, -1):解なし, (0, 1):任意
pair<ll, ll> crt1(ll a, ll b, ll m){
  if(m==0) return {0, -1};
  b=(b%m+m)%m;
  if(a==0) return (b==0?make_pair(0, 1):make_pair(0, -1));
  ll x, y, g=extgcd(a, m, x, y);
  if(b%g) return {0, -1};
  a/=g, b/=g, m/=g;
  extgcd(a, m, x, y);
  ll r=b*x%m; r=(r+m)%m;
  return make_pair(r, m);
}

//ax≡b mod m1, cx≡d mod m2
pair<ll, ll> crt2(ll a, ll b, ll m1, ll c, ll d, ll m2){
  auto [r1, n1]=crt1(a, b, m1); // x≡r1 mod n1
  auto [r2, n2]=crt1(c, d, m2); // x≡r2 mod n2
  if(n1==-1||n2==-1) return {0, -1};
  r1=(r1%n1+n1)%n1, r2=(r2%n2+n2)%n2;
  if(n1==1) return {r2, n2};
  if(n2==1) return {r1, n1};
  ll x, y;
  ll g=extgcd(n1, n2, x, y);
  if(r1%g!=r2%g) return {0, -1};
  ll D=(r2-r1)/g;
  ll n2g=n2/g, inv=(x%n2g+n2g)%n2g;
  ll t=(ll)((__int128)D*inv%n2g); t=(t+n2g)%n2g;
  __int128 lcm=(__int128)(n1/g)*n2;
  __int128 ans=r1+(__int128)n1*t; ans=((ans%lcm)+lcm)%lcm;
  return {ans, lcm};
}


int main(void){
  ll n; cin >> n;
  ll p, q, r, a, b, c; cin >> p >> q >> r >> a >> b >> c;
  //x=a mod p, x=b mod q -> x=r1 mod m1
  auto [r1, m1]=crt2(1, a, p, 1, b, q);
  //x=r1 mod m1, x=c mod r -> x=r2 mod m2
  auto [r2, m2]=crt2(1, r1, m1, 1, c, r);
  if(r2>n||m2==-1){
    cout << 0 << endl; return 0;
  }
  if(r2==0) cout << n+1 << endl;
  else cout << (n-r2)/m2+1 << endl;
  return 0; 
}
0