結果

問題 No.2280 FizzBuzz Difference
ユーザー SSRSSSRS
提出日時 2023-04-21 22:05:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 1,215 bytes
コンパイル時間 2,301 ms
コンパイル使用メモリ 201,388 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-24 08:13:01
合計ジャッジ時間 2,760 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 33 ms
5,376 KB
testcase_02 AC 39 ms
5,376 KB
testcase_03 AC 30 ms
5,376 KB
testcase_04 AC 39 ms
5,376 KB
testcase_05 AC 35 ms
5,376 KB
testcase_06 AC 37 ms
5,376 KB
testcase_07 AC 38 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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