a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits.
问一个区间内[l,r]有多少个Beautiful数字
范围9*10^18
思路一般，但是取模以及映射也是非常玄妙的
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define ll long long //dp[i][j][k][sta] means the first i nomber,whether it has limit,the val%2520,the lcm of ezch number ll pow[22],dp[22][2][2520][50]; int num[22],flcm[512],Map[2520],Map1[50],tmp[22],tot; int gcd(int a,int b) { if(!b) return a; return gcd(b,a%b); } int lcm(int a,int b) { if(a==0) return b; if(b==0) return a; return a*b/gcd(a,b); } void init() { pow[0]=1; for(int i=1;i<=18;i++) { pow[i]=pow[i-1]*10%2520; } for(int i=1;i<(1<<9);i++) for(int j=1;j<=9;j++) if(i&(1<<j-1)) flcm[i]=lcm(flcm[i-(1<<j-1)],j); for(int i=1;i<=(1<<9);i++) if(!Map[flcm[i]]) Map1[++tot]=flcm[i],Map[flcm[i]]=tot; } ll solve(ll x) { int len=0; ll ans=0; while(x) tmp[++len]=x%10,x/=10; for(int i=1;i<=len;i++) num[i]=tmp[len-i+1]; memset(dp,0,sizeof(dp)); dp[0][1][0][1]=1; for(int i=0;i<=len;i++) for(int j=0;j<2;j++) for(int k=0;k<2520;k++) for(int l=1;l<=tot;l++) { ll p=dp[i][j][k][l]; int pp=Map1[l]; if(!p) continue; if (i==len) { if (k % pp==0) ans+=p; continue; } if(!j) { for(int q=0;q<=9;q++) { dp[i+1][0][(k+q*pow[len-i-1])%2520][Map[lcm(pp,q)]]+=p; } }else { for(int q=0;q<num[i+1];q++) { dp[i+1][0][(k+q*pow[len-i-1])%2520][Map[lcm(pp,q)]]+=p; } dp[i+1][1][(k+num[i+1]*pow[len-i-1])%2520][Map[lcm(pp,num[i+1])]]+=p; } } return ans; } int main() { init(); int cas; scanf("%d",&cas); while(cas--) { ll a,b; scanf("%lld %lld",&a,&b); printf("%lld\n",solve(b)-solve(a-1)); } }
Input输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
Output对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input
1 100 0 0
Sample Output
80
水体不解释
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int dp[25][2][2],tmp[25],num[25]; int solve(int x) { int len=0,ans=0; while(x) tmp[++len]=x%10,x/=10; for(int i=1;i<=len;i++) num[len-i+1]=tmp[i]; memset(dp,0,sizeof(dp)); dp[0][1][0]=1; for(int i=0;i<=len;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) { int pp=dp[i][j][k]; if(!pp) continue; if(i==len) ans+=pp; if(!j) { if(!k) { for(int q=0;q<=9;q++) if(q!=6&&q!=4) dp[i+1][0][0]+=pp;else if(q!=4)dp[i+1][0][1]+=pp; }else for(int q=0;q<=9;q++) if(q!=6&&q!=2&&q!=4) dp[i+1][0][0]+=pp;else if(q==6) dp[i+1][0][1]+=pp; }else { if(!k) { for(int q=0;q<num[i+1];q++) if(q!=6&&q!=4) dp[i+1][0][0]+=pp;else if(q!=4)dp[i+1][0][1]+=pp; if(num[i+1]!=6&&num[i+1]!=4) dp[i+1][1][0]+=pp;else if(num[i+1]!=4)dp[i+1][1][1]+=pp; }else { for(int q=0;q<num[i+1];q++) if(q!=6&&q!=2&&q!=4) dp[i+1][0][0]+=pp;else if(q==6) dp[i+1][0][1]+=pp; if(num[i+1]!=6&&num[i+1]!=2&&num[i+1]!=4) dp[i+1][1][0]+=pp;else if(num[i+1]==6) dp[i+1][1][1]+=pp; } } } return ans; } int main() { int a,b; while(~scanf("%d %d",&a,&b)&&(a||b)) { printf("%d\n",solve(b)-solve(a-1)); } }
原文：http://www.cnblogs.com/dancer16/p/7719808.html