Beautiful numbers
Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with 阅读全文 »
hdu4389
05
12月
2015
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 <= 109), 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
Author
WHU
Source
2012 Multi-University Training Contest 9
题目类型：数位DP
算法分析：dp[pos][mod][d][sum]表示前i位数除以d得到余数mod且此时前i位和为sum的数字的个数，这里d在1~81范围内枚举，递归的边界是恰好满足d == sum且mod % sum == 0，最后累加所有的情况即可(枚举d)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
/************************************************* Author :supermaker Created Time :2015/12/4 23:45:43 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int dp[12][83][83][83], bit[66]; int SS (int pos, int mod, int d, int sum, bool flag) { if (pos == 0) return (d == sum && mod % sum == 0); if (flag && dp[pos][mod][d][sum] != -1) return dp[pos][mod][d][sum]; int res = 0; int x = flag ? 9 : bit[pos]; for (int i = 0; i <= x; i++) { int tt = (mod * 10 + i) % d; res += SS (pos - 1, tt, d, sum + i, flag || i < x); } return flag ? dp[pos][mod][d][sum] = res : res; } int Calc (int val) { int len = 0; while (val) { bit[++len] = val % 10; val /= 10; } int res = 0; for (int i = 1; i <= 81; i++) res += SS (len, 0, i, 0, 0); return res; } int main() { //CFF; //CPPFF; memset (dp, -1, sizeof (dp)); int t, id = 1; scanf ("%d", &t); while (t--) { int vala, valb; scanf ("%d%d", &vala, &valb); printf ("Case %d: %d\n", id++, Calc (valb) - Calc (vala - 1)); } return 0; } |