結果

問題 No.2280 FizzBuzz Difference
ユーザー SSRS
提出日時 2023-04-21 22:05:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 1,215 bytes
コンパイル時間 2,237 ms
コンパイル使用メモリ 201,044 KB
最終ジャッジ日時 2025-02-12 11:42:44
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
#include <atcoder/math>
using namespace std;
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    long long M, A, B, K;
    cin >> M >> A >> B >> K;
    long long L = lcm(A, B);
    if (K > A){
      cout << 0 << endl;
    } else if (K == A){
      long long ans = 0;
      if (K == A){
        ans += M / A - 1 - (M / B - M / L);
        if (M / B * B > M / A * A){
          ans++;
        }
      }
      cout << ans << endl;
    } else {
      long long ans = 0;
      vector<long long> r1 = {0, K}, m1 = {B, A};
      pair<long long, long long> P1 = atcoder::crt(r1, m1);
      if (P1.second != 0){
        if (P1.first <= M){
          ans += (M - P1.first) / P1.second + 1;
        }
        if (P1.first <= A + K - 1){
          ans -= (A + K - 1 - P1.first) / P1.second + 1;
        }
      }
      vector<long long> r2 = {0, K}, m2 = {A, B};
      pair<long long, long long> P2 = atcoder::crt(r2, m2);
      if (P2.second != 0){
        if (P2.first <= M){
          ans += (M - P2.first) / P2.second + 1;
        }
        if (P2.first <= B + K - 1){
          ans -= (B + K - 1 - P2.first) / P2.second + 1;
        }
      }
      cout << ans << endl;
    }
  }
}
0