結果

問題 No.2280 FizzBuzz Difference
ユーザー 沙耶花沙耶花
提出日時 2023-04-22 11:57:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 4,100 bytes
コンパイル時間 2,292 ms
コンパイル使用メモリ 199,256 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-24 16:36:48
合計ジャッジ時間 3,302 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#ifndef ATCODER_MATH_HPP
#define ATCODER_MATH_HPP 1

#include <algorithm>
#include <cassert>
#include <tuple>
#include <vector>

#include "atcoder/internal_math"

namespace atcoder {

long long pow_mod(long long x, long long n, int m) {
    assert(0 <= n && 1 <= m);
    if (m == 1) return 0;
    internal::barrett bt((unsigned int)(m));
    unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m));
    while (n) {
        if (n & 1) r = bt.mul(r, y);
        y = bt.mul(y, y);
        n >>= 1;
    }
    return r;
}

long long inv_mod(long long x, long long m) {
    assert(1 <= m);
    auto z = internal::inv_gcd(x, m);
    assert(z.first == 1);
    return z.second;
}

// (rem, mod)
std::pair<long long, long long> crt(const std::vector<long long>& r,
                                    const std::vector<long long>& m) {
    assert(r.size() == m.size());
    int n = int(r.size());
    // Contracts: 0 <= r0 < m0
    long long r0 = 0, m0 = 1;
    for (int i = 0; i < n; i++) {
        assert(1 <= m[i]);
        long long r1 = internal::safe_mod(r[i], m[i]), m1 = m[i];
        if (m0 < m1) {
            std::swap(r0, r1);
            std::swap(m0, m1);
        }
        if (m0 % m1 == 0) {
            if (r0 % m1 != r1) return {0, 0};
            continue;
        }
        // assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        // (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        // r2 % m0 = r0
        // r2 % m1 = r1
        // -> (r0 + x*m0) % m1 = r1
        // -> x*u0*g = r1-r0 (mod u1*g) (u0*g = m0, u1*g = m1)
        // -> x = (r1 - r0) / g * inv(u0) (mod u1)

        // im = inv(u0) (mod u1) (0 <= im < u1)
        long long g, im;
        std::tie(g, im) = internal::inv_gcd(m0, m1);

        long long u1 = (m1 / g);
        // |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if ((r1 - r0) % g) return {0, 0};

        // u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        long long x = (r1 - r0) / g % u1 * im % u1;

        // |r0| + |m0 * x|
        // < m0 + m0 * (u1 - 1)
        // = m0 + m0 * m1 / g - m0
        // = lcm(m0, m1)
        r0 += x * m0;
        m0 *= u1;  // -> lcm(m0, m1)
        if (r0 < 0) r0 += m0;
    }
    return {r0, m0};
}

long long floor_sum(long long n, long long m, long long a, long long b) {
    unsigned long long ans = 0;
    if (a < 0) {
        unsigned long long a2 = internal::safe_mod(a, m);
        ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);
        a = a2;
    }
    if (b < 0) {
        unsigned long long b2 = internal::safe_mod(b, m);
        ans -= 1ULL * n * ((b2 - b) / m);
        b = b2;
    }
    return ans + internal::floor_sum_unsigned(n, m, a, b);
}

}  // namespace atcoder

#endif  // ATCODER_MATH_HPP

using namespace atcoder;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 8000000000000000001

long long get(long long M,long long A,long long B,long long K){
	long long ans = 0;
	if(A<K){
	}
	else if(A==K){
		ans = (M/A)-1 - ((M/A)*A/B);
		ans += M / lcm(A,B);
	}
	else{
		long long ret = 0;
		long long n = (M-K)/A;
		ret -= floor_sum(n,B,A,A);
		ret += floor_sum(n,B,A,A+K);
		ret += floor_sum(n,B,A,A);
		ret -= floor_sum(n,B,A,A+K-1);
		n = M/A;
		ret += floor_sum(n,B,A,A);
		ret -= floor_sum(n,B,A,A-K-1);
		ret -= floor_sum(n,B,A,A);
		ret += floor_sum(n,B,A,A-K);
		ans = ret;
	}
	return ans;
}

long long gu(long long M,long long A,long long B,long long K){
	long long ret = 0;
	long long last = -Inf64;
	for(long long i=1;i<=M;i++){
		if(i%A==0||i%B==0){
			if(i-last==K)ret++;
			last = i;
		}
	}
	return ret;
}
int main(){
	/*
	for(int i=1;i<=10;i++){
		for(int j=1;j<=i;j++){
			for(int k=j+1;k<=10;k++){
				for(int l=1;l<=10;l++){
					if(get(i,j,k,l)!=gu(i,j,k,l)){
						cout<<i<<','<<j<<','<<k<<','<<l<<endl;
						cout<<get(i,j,k,l)<<','<<gu(i,j,k,l)<<endl;
						return 0;
					}
				}
			}
		}
	}
	
	*/
	int _t;
	cin>>_t;
	rep(_,_t){
		
		long long M,A,B,K;
		cin>>M>>A>>B>>K;
		cout<<get(M,A,B,K)<<endl;
		//cout<<gu(M,A,B,K)<<endl;
	}
	
	return 0;
}
0