結果

問題 No.2032 Let's Write Multiples!!
ユーザー ygussanyygussany
提出日時 2022-07-24 19:01:48
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 2,504 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 37,108 KB
実行使用メモリ 13,880 KB
最終ジャッジ日時 2024-07-06 14:09:32
合計ジャッジ時間 7,401 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,880 KB
testcase_01 AC 1,050 ms
6,940 KB
testcase_02 AC 40 ms
6,940 KB
testcase_03 AC 25 ms
6,940 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
#include <stdio.h>

const int dig[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

int gcd(int a, int b)
{
	if (a == 0) return b;
	else return gcd(b % a, a);
}

int solve(int R, int K, int C)
{
	static int r[10], lower[10], upper[10], dig_mod[10];
	int d, i, j, k, l, m, g, dd, KK, RR, ans = 0;
	for (d = 0, RR = R; RR > 0; d++, RR /= 10) {
		r[d] = RR % 10;
		dig_mod[d] = dig[d] % K;
	}
	for (i = 1, lower[0] = 0; i < d; i++) lower[i] = lower[i-1] + r[i-1] * dig[i-1];
	for (i = d - 2, upper[d-1] = 0; i >= 0; i--) upper[i] = upper[i+1] * 10 + r[i+1];
	for (i = d - 1; i >= 0; i--) {
		if (upper[i] < 10000) {
			l = dig[i] % K;
			m = dig[i] / K;
			for (j = 0, k = (K - C * dig[i] % K) % K; j < upper[i]; j++, k -= dig_mod[i+1]) {
				if (k < 0) k += K;
				if (k < l) ans += m + 1;
				else ans += m;
			}
			if (r[i] >= C) {
				if (k < 0) k += K;
				if (r[i] == C) {
					l = (lower[i] + 1) % K;
					m = (lower[i] + 1) / K;
				}
				if (k < l) ans += m + 1;
				else ans += m;
			}
		} else {
			g = gcd(K, dig_mod[i+1]);
			KK = K / g;
			dd = dig_mod[i+1] / g;
			for (j = 0, k = (K - C * dig[i] % K) % K; j < dig[i]; j++, k--) {
				if (k < 0) k += K;
				if (k % g == 0) break;
			}
			if (k % g != 0) continue;
			k /= g;
			l = (upper[i] + 1) % KK;
			m = (upper[i] + 1) / KK;
			for (; j < lower[i]; j += g, k--) {
				if (k < 0) k += KK;
				if (dd == 0) {
					if (k == 0) ans += upper[i] + 1;
				} else if (div_mod(k, dd, KK) < l) ans += m + 1;
				else ans += m;
			}
			if (j == lower[i]) {
				if (k < 0) k += KK;
				if (r[i] < C) {
					l = upper[i] % KK;
					m = upper[i] / KK;
				}
				if (dd == 0) {
					if (k == 0) ans += upper[i] + ((r[i] >= C)? 1: 0);
				} else if (div_mod(k, dd, KK) < l) ans += m + 1;
				else ans += m;
				j += g;
				k--;
			}
			l = upper[i] % KK;
			m = upper[i] / KK;
			for (; j < dig[i]; j += g, k--) {
				if (k < 0) k += KK;
				if (dd == 0) {
					if (k == 0) ans += upper[i] + 1;
				} else if (div_mod(k, dd, KK) < l) ans += m + 1;
				else ans += m;
			}
		}
	}
	return ans;
}

int main()
{
	int T, L, R, K, C;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d", &L, &R, &K, &C);
		printf("%d\n", solve(R, K, C) - solve(L - 1, K, C));
	}
	fflush(stdout);
	return 0;
}
0