#862040 (C++17) No.2280 FizzBuzz Difference

• 問題: No.2280 FizzBuzz Difference
• ユーザー: 沙耶花
• 提出日時: 2023-04-22 11:57:22
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 57 ms / 2,000 ms
• コード長: 4,100 bytes
• コンパイル時間: 2,169 ms
• コンパイル使用メモリ: 206,032 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-07 01:16:37
• 合計ジャッジ時間: 3,058 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	46 ms; 5,248 KB
testcase_02	AC	57 ms; 5,248 KB
testcase_03	AC	34 ms; 5,248 KB
testcase_04	AC	57 ms; 5,248 KB
testcase_05	AC	48 ms; 5,248 KB
testcase_06	AC	49 ms; 5,248 KB
testcase_07	AC	56 ms; 5,248 KB

ソースコード

#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;
}