結果

問題 No.2032 Let's Write Multiples!!
コンテスト
ユーザー 👑 ygussany
提出日時 2022-07-24 19:17:02
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 2,168 ms / 3,000 ms
コード長 2,470 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 32,588 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-21 08:34:13
合計ジャッジ時間 28,551 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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