Submission #50024037

---

Source Code Expand

#include <stdio.h>
#include <inttypes.h>

char N[32];

int mod;
int memo_mod[32][2][10 * 32][10 * 32];
uint64_t memo[32][2][10 * 32][10 * 32];

uint64_t calc(int pos, int sati, int sum_mod, int digit_sum) {
	uint64_t ans = 0;
	int limit, i;
	if (N[pos] == '\0') return sum_mod == 0 && digit_sum == mod;
	if (digit_sum > mod) return 0;
	if (memo_mod[pos][sati][sum_mod][digit_sum] == mod) {
		return memo[pos][sati][sum_mod][digit_sum];
	}
	limit = sati ? N[pos] - '0' : 9;
	for (i = 0; i <= limit; i++) {
		ans += calc(pos + 1, sati && i == limit, (sum_mod * 10 + i) % mod, digit_sum + i);
	}
	memo[pos][sati][sum_mod][digit_sum] = ans;
	memo_mod[pos][sati][sum_mod][digit_sum] = mod;
	return ans;
}

int main(void) {
	int i;
	int max = 0;
	uint64_t ans = 0;
	if (scanf("%31s", N) != 1) return 1;
	for (i = 0; N[i] != '\0'; i++) max += 9;
	for (i = 1; i <= max; i++) {
		mod = i;
		ans += calc(0, 1, 0, 0);
	}
	printf("%" PRIu64 "\n", ans);
	return 0;
}

Submission Info

Judge Result