X mod f(x)

Problem Description Here is a function f(x):　　　int f ( int x ) {　　　 if ( x == 0 ) return 0;　　　 return f ( x / 10 ) + x % 10;　　　} 　　　Now, you want to know, in a given interval [A, B] (1 <= A <= B <= 10 ⁹), how many integer x that mod f(x) equal to 0.  

 

Input 　　　The first line has an integer T (1 <= T <= 50), indicate the number of test cases. 　　　Each test case has two integers A, B.  

 

Output 　　　For each test case, output only one line containing the case number and an integer indicated the number of x.  

 

Sample Input 2 1 10 11 20  

 

Sample Output Case 1: 10 Case 2: 3   f(x)是x各位上的数的和，求一个范围内，有多少x使得x mod f(x) == 0。   f(x)显然最多只有81,遍历81种值就可以来数位dp了。   #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define ll long long int n; int dp[10][81][81][81]; int dig[10]; int dfs(int pos, int num, int mod, int sum, int lim) { if(pos == -1) return sum == mod && num == 0; if(!lim && dp[pos][sum][mod][num] != -1) return dp[pos][sum][mod][num]; int End = lim ? dig[pos] : 9; int ret = 0; for(int i = 0; i <= End; i++) { ret += dfs(pos - 1, (num * 10 + i) % mod, mod, sum + i, lim && (i == End)); } if(!lim) dp[pos][sum][mod][num] = ret; return ret; } int func(int num) { int n = 0; while(num) { dig[n++] = num % 10; num /= 10; } int ret = 0; for(int i = 1; i <= 81; i++) ret += dfs(n - 1, 0, i, 0, 1); return ret; } int main() { int t; int val = 0; scanf("%d", &t); memset(dp, -1, sizeof(dp)); // sb le while(t--) { int a, b; scanf("%d %d", &a, &b); printf("Case %d: %d\n", ++val, func(b) - func(a - 1)); } }

 

转载于:https://www.cnblogs.com/lonewanderer/p/5661645.html

相关资源：JAVA上百实例源码以及开源项目