結果

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

ソースコード

diff #
プレゼンテーションモードにする

#line 1 "..\\Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <atcoder/modint>
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\gcd.hpp"
#line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\gcd.hpp"
namespace nachia{
template<class Int> Int Gcd(Int a, Int b){
if(a < 0) a = -a;
if(b < 0) b = -b;
if(!a || !b) return a + b;
while(b){ a %= b; std::swap(a, b); }
return a;
}
}
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math-modulo\\dynamic-mod-supply.hpp"
#include <cassert>
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\ext-gcd.hpp"
#include <utility>
#line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math\\ext-gcd.hpp"
namespace nachia{
// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
long long x = 1, y = 0;
while(b){
long long u = a / b;
std::swap(a-=b*u, b);
std::swap(x-=y*u, y);
}
return std::make_pair(x, a);
}
} // namespace nachia
#line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math-modulo\\dynamic-mod-supply.hpp"
namespace nachia{
class DynamicModSupplier{
using u64 = unsigned long long;
using u128 = unsigned __int128;
using Int = unsigned int;
private:
u64 imod;
Int mod;
// atcoder library
u64 reduce2(u64 z) const noexcept {
// atcoder library
#ifdef _MSC_VER
u64 x; _umul128(z, im, &x);
#else
u64 x = (u64)(((u128)(z)*imod) >> 64);
#endif
return z - x * mod;
}
Int reduce(u64 z) const noexcept {
Int v = reduce2(z);
if(mod <= v) v += mod;
return v;
}
public:
DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) {
assert(2 <= MOD);
assert(MOD < (1u << 31));
imod = (u64)(-1) / mod + 1;
}
Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; }
Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; }
Int mul(Int a, Int b) const { return reduce((u64)a * b); }
Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); }
Int inv(Int a) const {
Int v = ExtGcd(a, mod).first;
return (v < mod) ? v : (v + mod);
}
Int pow(Int a, u64 i) const {
Int r = a, ans = 1;
while(i){
if(i & 1) ans = mul(ans, r);
i /= 2;
r = mul(r, r);
}
return ans;
}
Int getMod() const { return mod; }
};
} // namespace nachia
#line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\math-modulo\\garner.hpp"
namespace nachia{
template<class FinishType>
struct GarnerMod{
using Int = unsigned int;
using IntLong = unsigned long long;
std::vector<Int> mods;
std::vector<DynamicModSupplier> dynmods;
std::vector<std::vector<Int>> table_coeff;
std::vector<Int> table_coeffinv;
void precalc(std::vector<Int> new_mods){
mods = std::move(new_mods);
dynmods.resize(mods.size());
for(size_t i=0; i<mods.size(); i++) dynmods[i] = DynamicModSupplier(mods[i]);
int nmods = mods.size();
table_coeff.assign(nmods+1, std::vector<Int>(nmods, 1));
for(int j=0; j<nmods; j++){
for(int k=0; k<nmods; k++) table_coeff[j+1][k] = table_coeff[j][k];
for(int k=j+1; k<nmods; k++) table_coeff[j+1][k] = dynmods[k].mul(table_coeff[j+1][k], mods[j] % mods[k]);
}
table_coeffinv.resize(nmods);
for(int i=0; i<nmods; i++) table_coeffinv[i] = dynmods[i].inv(table_coeff[i][i]);
}
FinishType calc(const std::vector<Int>& x){
int nmods = mods.size();
std::vector<Int> table_const(nmods);
FinishType res = 0;
FinishType res_coeff = 1;
for(int j=0; j<nmods; j++){
Int t = dynmods[j].mul(dynmods[j].sub(x[j], table_const[j]), table_coeffinv[j]);
for(int k=j+1; k<nmods; k++){
table_const[k] = dynmods[k].muladd(t, table_coeff[j][k], table_const[k]);
}
res += res_coeff * FinishType(t);
res_coeff *= mods[j];
}
return res;
}
std::vector<FinishType> calc(std::vector<std::vector<Int>> x){
int n = x[0].size(), m = x.size();
std::vector<FinishType> res(n);
std::vector<Int> buf(m);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++) buf[j] = x[j][i];
res[i] = calc(buf);
}
return res;
}
};
} // namespace nachia
#line 8 "..\\Main.cpp"
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;
i64 solve(i64 M, i64 A, i64 B, i64 K){
if(K > A) return 0;
{
i64 g = nachia::Gcd(A, B);
if(g != 1){
if(K % g != 0) return 0;
return solve(M/g, A/g, B/g, K/g);
}
}
if(K == A){
M = M / A * A;
i64 cntA = M / A;
i64 cntB = M / B;
i64 cntAB = M / (A*B);
return cntA - 1 - cntB + cntAB;
}
auto garner = nachia::GarnerMod<u64>();
garner.precalc({ (u32)A, (u32)B });
i64 AB = A * B;
i64 t1 = garner.calc({ (u32)0, (u32)K });
i64 t2 = garner.calc({ (u32)K, (u32)0 });
i64 ans = (M + AB - t1) / AB + (M + AB - t2) / AB;
return ans;
}
int main(){
int T; cin >> T;
rep(t,T){
i64 M, A, B, K; cin >> M >> A >> B >> K;
cout << solve(M, A, B, K) << '\n';
}
return 0;
}
struct ios_do_not_sync{
ios_do_not_sync(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
} ios_do_not_sync_instance;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0