[UVA][dp] 11361 - Investigating Div-Sum Property
|
An integer is divisible by 3 if the sum of its digits is also divisible by 3. For example, 3702 is divisible by 3 and 12(3+7+0+2) is also divisible by 3. This property also holds for the integer 9.
In this problem, we will investigate this property for other integers.
Input
The first line of input is an integer T(T<100) that indicates the number of test cases. Each case is a line containing 3 positive integers A, B and K. 1 <= A <= B < 2^31 and 0<K<10000.
Output
For each case, output the number of integers in the range [A, B] which is divisible by K and the sum of its digits is also divisible by K.
|
Sample Input |
Output for Sample Input |
|
3 1 20 1 1 20 2 1 1000 4 |
20 5 64 |
ProblemSetter: Sohel Hafiz
Special Thanks: Ivan Krasilnikov
題目描述：
找到區間 [A, B] 符合被 K 整除且每一位數總和也被 K 整除 的個數。
題目解法：
dp[數字長][數字 mod K][位數總和 mod K]
仔細思考一下， 2147483647 中，K 最大為 82 左右，
因此對於 K > 100 答案肯定為 0。
現在將題目改成 f(B)-f(A-1) 去簡化它。
狀態還是如上描述，不會對於有邊界條件的處理就稍微麻煩了點。
當我們對於 A = 123456 計算 [0, 123456] 的答案時，
將當於考慮 6 位數字
000000 - 123456
但是最高位無法放上比 1 大的數字，以此類推。
因此當我們還在計算上界時，則無法將狀態記錄到陣列中。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
// 2147483647 => 1999999999 max sum 82
int dp[15][105][105];
char digit[50];
int A, B, K;
int dfs(int d, int s, int ds, int onlimit) {
if(d == 0) return s == 0 && ds == 0;
if(onlimit == 0 && dp[d][s][ds] != -1)
return dp[d][s][ds];
int ret = 0;
int i;
for(i = onlimit ? digit[d]-'0' : 9; i >= 0; i--) {
ret += dfs(d-1, (s*10 + i)%K, (ds+i)%K, onlimit && i == digit[d]-'0');
}
return onlimit ? ret : dp[d][s][ds] = ret;
}
int solve(int A) {
memset(dp, -1, sizeof(dp));
sprintf(digit+1, "%d", A);
int len = strlen(digit+1);
int i, j;
for(i = 1, j = len; i < j; i++, j--)
swap(digit[i], digit[j]);
int ret = dfs(len, 0, 0, 1);
return ret;
}
int main() {
int testcase;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &A, &B, &K);
if(K >= 100)
puts("0");
else {
int a = solve(A-1);
int b = solve(B);
printf("%d\n", b-a);
}
}
return 0;
}