D. Beautiful numbers
链接 http://codeforces.com/contest/55/problem/D
分析:
代码:
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<cmath>
- #include<iostream>
- #include<cctype>
- #include<set>
- #include<queue>
- #include<vector>
- #include<map>
- using namespace std;
- typedef long long LL;
- inline LL read() {
- LL x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
- for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
- }
- const int N = 2520;
- LL dp[30][50][N + 10];
- int num[50]={0,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520};
- int a[30], pos[N + 10];
- int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); }
- int getlcm(int a,int b) { return a * b / gcd(a, b); }
- LL dfs(int p,int lcm,int now,bool lim) {
- if (p == 0) return lcm && now % num[lcm] == 0;
- if (!lim && ~dp[p][lcm][now]) return dp[p][lcm][now];
- int u = lim ? a[p] : 9;
- LL ans = 0;
- for (int i = 0; i <= u; ++i) {
- int t = lcm ? pos[getlcm(num[lcm], max(i, 1))] : i;
- ans += dfs(p - 1, t, (now * 10 + i) % N, lim && i == u);
- }
- if (!lim) dp[p][lcm][now] = ans;
- return ans;
- }
- LL solve(LL x) {
- if (x <= 0) return 0;
- int pos = 0;
- while (x) {
- a[++pos] = x % 10; x /= 10;
- }
- return dfs(pos, 0, 0, 1);
- }
- int main() {
- memset(dp, -1, sizeof(dp));
- for (int i = 0; i < 49; ++i) pos[num[i]] = i;
- for (int T = read(); T --; ) {
- LL x = read(), y = read();
- cout << (solve(y) - solve(x - 1)) << "\n";
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2990926.html