結果
問題 | No.2280 FizzBuzz Difference |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#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 libraryu64 reduce2(u64 z) const noexcept {// atcoder library#ifdef _MSC_VERu64 x; _umul128(z, im, &x);#elseu64 x = (u64)(((u128)(z)*imod) >> 64);#endifreturn 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;