結果

問題 No.2280 FizzBuzz Difference
ユーザー hongrockhongrock
提出日時 2023-04-21 23:52:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,274 bytes
コンパイル時間 2,095 ms
コンパイル使用メモリ 195,668 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-24 09:43:24
合計ジャッジ時間 2,736 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 13 ms
5,376 KB
testcase_02 AC 17 ms
5,376 KB
testcase_03 AC 10 ms
5,376 KB
testcase_04 AC 18 ms
5,376 KB
testcase_05 AC 14 ms
5,376 KB
testcase_06 AC 15 ms
5,376 KB
testcase_07 AC 16 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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 c = a / __gcd(a, b);
    ll ans = m / a - 1;
    ll cnt = m / v;
    ans = ans - cnt * (c - 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