結果

問題 No.2280 FizzBuzz Difference
コンテスト
ユーザー hongrock
提出日時 2023-04-21 23:50:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,246 bytes
コンパイル時間 1,864 ms
コンパイル使用メモリ 194,320 KB
最終ジャッジ日時 2025-02-12 12:38:24
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for(int i=(a); i<(n); ++i)
#define per(i, a, n) for(int i=(a); i>(n); --i)
#define pb emplace_back
#define mp make_pair
#define clr(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x & -x)
#define fi first
#define se second
#define lson o<<1
#define rson o<<1|1
#define gmid l[o]+r[o]>>1
 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll, ll>;
using ui = unsigned int;
using i128 = __int128;
 
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr double EPS = 1e-8;
const double PI = acos(-1.0);

constexpr int N = 2e5 + 10;

int T;
ll a, b, m, k;

void exgcd(ll a, ll b, ll &d, ll &x, ll &y){
  if(!b){
    d = a; x = 1; y = 0;
  } else {
    exgcd(b, a%b, d, y, x);
    y -= x * (a / b);
  }
}

ll solve(){
  if(k > a) return 0;
  if(b % a == 0){
    if(k != a)  return 0;
    return m / a - 1;
  }
  ll v = lcm(a, b);
  if(k == a){
    ll ans = m / a - 1;
    ll cnt = m / v;
    ans = ans - cnt * (a - 1);
    m = m % v;
    if(m >= b){
      if(m / b * b < m / a * a){
        ans = ans - m / b;
      } else {
        ans = ans - m / b + 1;
      }
    }
    return ans;
  }

  ll g = __gcd(a, b);  
  if(k % g) return 0;

  ll d, x, y;
  exgcd(a / g, b / g, d, x, y);

  i128 v1 = abs(a / g * x), v2 = abs(b / g * y);

  ll ans = 0;

  if(v1 > v2) swap(v1, v2);
  v1 = v1 * k;
  v2 = v2 * k;
  v2 = v2 - (v1 / v) * v;
  if(m >= v2){
    ans = ans + (m - v2) / v + 1;
  }

  if(x < 0){
    ll c = y / (a / g);
    x += c * (b / g);
    y -= c * (a / g);
    if(y > 0){
      x += (b / g);
      y -= (a / g);
    }
  } else {
    ll c = x / (b / g);
    x -= c * (b / g);
    y += c * (a / g);
    if(x > 0){
      x -= (b / g);
      y += (a / g);
    }
  }

  v1 = abs(a / g * x);
  v2 = abs(b / g * y);
  
  if(v1 > v2) swap(v1, v2);
  
  v1 = v1 * k;
  v2 = v2 * k;
  v2 = v2 - (v1 / v) * v;
  if(m >= v2){
    ans = ans + (m - v2) / v + 1;
  }

  return ans;
}

void _main(){
  cin >> T;
  while(T--){
    cin >> m >> a >> b >> k;
    cout << solve() << '\n';
  }
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  _main();
  return 0;
}
0