結果

問題 No.2032 Let's Write Multiples!!
ユーザー 👑 ygussanyygussany
提出日時 2022-07-24 19:17:02
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 1,694 ms / 3,000 ms
コード長 2,470 bytes
コンパイル時間 864 ms
コンパイル使用メモリ 31,020 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-28 13:53:39
合計ジャッジ時間 23,439 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 964 ms
4,376 KB
testcase_02 AC 39 ms
4,376 KB
testcase_03 AC 25 ms
4,380 KB
testcase_04 AC 1,204 ms
4,376 KB
testcase_05 AC 1,199 ms
4,376 KB
testcase_06 AC 1,177 ms
4,380 KB
testcase_07 AC 868 ms
4,380 KB
testcase_08 AC 857 ms
4,376 KB
testcase_09 AC 1,694 ms
4,376 KB
testcase_10 AC 864 ms
4,380 KB
testcase_11 AC 862 ms
4,380 KB
testcase_12 AC 895 ms
4,376 KB
testcase_13 AC 855 ms
4,376 KB
testcase_14 AC 819 ms
4,380 KB
testcase_15 AC 1,203 ms
4,380 KB
testcase_16 AC 1,199 ms
4,376 KB
testcase_17 AC 1,206 ms
4,376 KB
testcase_18 AC 1,202 ms
4,376 KB
testcase_19 AC 1,125 ms
4,376 KB
testcase_20 AC 518 ms
4,376 KB
testcase_21 AC 616 ms
4,380 KB
testcase_22 AC 618 ms
4,380 KB
testcase_23 AC 618 ms
4,380 KB
testcase_24 AC 616 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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, inv;
	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;
			
			if (dd == 0) {
				k /= g;
				for (; j <= lower[i]; j += g, k--) {
					if (k < 0) k += KK;
					if (k == 0) ans += upper[i] + ((r[i] >= C)? 1: 0);
				}
				for (; j < dig[i]; j += g, k--) {
					if (k < 0) k += KK;
					if (k == 0) ans += upper[i] + ((r[i] > C)? 1: 0);
				}
				continue;
			}
			
			inv = div_mod(1, dd, KK);
			k = (long long)k / g * inv % KK;
			if (r[i] < C) {
				l = upper[i] % KK;
				m = upper[i] / KK;
			} else {
				l = (upper[i] + 1) % KK;
				m = (upper[i] + 1) / KK;
			}
			for (; j <= lower[i]; j += g, k -= inv) {
				if (k < 0) k += KK;
				if (k < l) ans += m + 1;
				else ans += m;
			}
			if (r[i] <= C) {
				l = upper[i] % KK;
				m = upper[i] / KK;
			}
			for (; j < dig[i]; j += g, k -= inv) {
				if (k < 0) k += KK;
				if (k < 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