CF55D

传送门

简要题意

定义一个正整数为美丽的当且仅当这个数能被所有非零位上的数整除。 给定ll,rr,求llrr中有多少数是美丽的。 多组数据,l,r9×1018l,r\le 9\times 10^{18}

简要题解

数位DP。 “美丽”的数要求被所有非零位上的数整除,也就是2,3,4,...,92,3,4,...,9这些数字如果出现了一定能整除这个数。 所以我们可以用0..2810..2^8-1来记录每个数字的出现情况(是否出现)

要求被这些数整除,就相当于被它们的最小公倍数整除。

因为LCM(2,3,4,...,9)=2520LCM(2,3,4,...,9)=2520,所以我们可以考虑这个数 的值,如果这个值能被这些数位整除,那么原数一定能被这些数位整除。

dp[i][j][k]dp[i][j][k]表示计算到从低到高第ii位,前面的数 2..92..9的出现情况是kk,并且不是边界情况的方案数。

利用记忆化搜索。 记dfs(j,k,i,bj)dfs(j,k,i,bj)表示计算到从低到高第ii位,前面的数 2..92..9的出现情况是kk,如果bj=1bj=1则是边界情况,否则不是的方案数。

详细写法见代码。 注意:

  1. CF机子用的是windows,要用%I64d或cin/cout输入输出。
  2. CF机子估计是32位的,尽量不要用long long,否则可能会TLE on Test 8
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
/*
Author: CNYALI_LK
LANG: C++
PROG: CF55D.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define aint(x) x.begin(),x.end()
#define end(...) {printf(__VA_ARGS__);exit(0);}
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int a[102],t;
ll dp[20][2560][300];
ll dfs(int md,int cx,int w,int bj){
if(!bj&&dp[w][md][cx]+1)return dp[w][md][cx];
if(w==0){
for(int i=0;i<8;++i){
if((cx&(1<<i))&&(md%(i+2))){
return dp[w][md][cx]=0;
}
}
return dp[w][md][cx]=1;
}
if(bj){
ll ans=0;
for(int i=0;i<a[w];++i){
if(i<2){
ans+=dfs((md*10+i)%2520,cx,w-1,0);
}
else ans+=dfs((md*10+i)%2520,cx|(1<<(i-2)),w-1,0);
}
if(a[w]<2)ans+=dfs((md*10+a[w])%2520,cx,w-1,1);
else ans+=dfs((md*10+a[w])%2520,cx|(1<<(a[w]-2)),w-1,1);
return ans;
}
else{
dp[w][md][cx]=0;
for(int i=0;i<10;++i){
if(i<2){
dp[w][md][cx]+=dfs((md*10+i)%2520,cx,w-1,0);
}
else dp[w][md][cx]+=dfs((md*10+i)%2520,cx|(1<<(i-2)),w-1,0);
}
return dp[w][md][cx];

}
}
ll f(ll x){
t=0;
while(x){
a[++t]=x%10;
x/=10;
}
return dfs(0,0,t,1);
}
int main(){
#ifdef cnyali_lk
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ll t,l,r;
cin>>t;
memset(dp,-1,sizeof(dp));
while(t){
--t;
cin>>l>>r;
cout<<f(r)-f(l-1)<<endl;
}
return 0;
}
文章目录
  1. 1. 简要题意
  2. 2. 简要题解
|

博客使用Disqus作为评论系统