結果
問題 | No.2032 Let's Write Multiples!! |
ユーザー |
👑 ![]() |
提出日時 | 2022-08-05 21:34:07 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 385 ms / 3,000 ms |
コード長 | 3,740 bytes |
コンパイル時間 | 2,635 ms |
コンパイル使用メモリ | 116,200 KB |
最終ジャッジ日時 | 2025-01-30 17:45:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <atcoder/modint>#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 < m0long 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 % (u1*g) = (r1 - r0) (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) {long long ans = 0;if (a >= m) {ans += (n - 1) * n * (a / m) / 2;a %= m;}if (b >= m) {ans += n * (b / m);b %= m;}long long y_max = (a * n + b) / m, x_max = (y_max * m - b);if (y_max == 0) return ans;ans += (n - (x_max + a - 1) / a) * y_max;ans += floor_sum(y_max, a, m, (a - x_max % a) % a);return ans;}} // namespace atcoder#endif // ATCODER_MATH_HPPusing namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using modint = atcoder::static_modint<998244353>;int main(){int T; cin >> T;while(T --> 0){i64 L, R, K, C; cin >> L >> R >> K >> C;L = (L + K - 1) / K * K;if(L > R){ cout << "0\n"; continue; }i64 N = (R - L) / K + 1;i64 ans = 0;for(i64 d = 1; d <= 1'000'000'000; d *= 10){i64 s = atcoder::floor_sum(N, d*10, K, L+(9-C)*d);i64 t = atcoder::floor_sum(N, d*10, K, L+(10-C)*d);ans += t - s;}cout << ans << '\n';}return 0;}struct ios_do_not_sync{ios_do_not_sync(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);}} ios_do_not_sync_instance;