#include <bits/stdc++.h> using namespace std; long long dp[19][1024][8][9][5][7]; long long calc(long long n) { for(int i1=0;i1<19;i1++)for(int i2=0;i2<1024;i2++)for(int i3=0;i3<8;i3++)for(int i4=0;i4<9;i4++)for(int i5=0;i5<5;i5++)for(int i6=0;i6<7;i6++)dp[i1][i2][i3][i4][i5][i6]=0; int len=0; long long N=n; int d[20]={0}; while(N>0) { d[len]=N%10; N/=10; len++; } if(len==0)return 0; len--; for(int i=1;i<d[len];i++)dp[len][1<<i][i%8][i%9][i%5][i%7]++; len--; long long pref=d[len+1]; int msk=(1<<d[len+1]); for(;len>=0;len--) { for(int i=1;i<=9;i++)dp[len][1<<i][i%8][i%9][i%5][i%7]++; for(int i2=0;i2<1024;i2++)for(int i3=0;i3<8;i3++)for(int i4=0;i4<9;i4++)for(int i5=0;i5<5;i5++)for(int i6=0;i6<7;i6++) { for(int k=1;k<=9;k++) { dp[len][i2|(1<<k)][(10*i3+k)%8][(10*i4+k)%9][(10*i5+k)%5][(10*i6+k)%7]+=dp[len+1][i2][i3][i4][i5][i6]; } // dp[len][msk][pref%8][pref%9][pref%5][pref%7]++; } for(int k=1;k<d[len];k++)dp[len][msk|(1<<k)][(10*pref+k)%8][(10*pref+k)%9][(10*pref+k)%5][(10*pref+k)%7]++; pref=10*pref+d[len]; msk|=(1<<d[len]); } dp[0][msk][pref%8][pref%9][pref%5][pref%7]++; long long res=0; for(int i2=0;i2<1024;i2++)for(int i3=0;i3<8;i3++)for(int i4=0;i4<9;i4++)for(int i5=0;i5<5;i5++)for(int i6=0;i6<7;i6++) { int flag=0; if((i2&(1<<0))!=0)flag=1; else if((i2&(1<<2))!=0&&i3%2!=0)flag=1; else if((i2&(1<<3))!=0&&i4%3!=0)flag=1; else if((i2&(1<<4))!=0&&i3%4!=0)flag=1; else if((i2&(1<<5))!=0&&i5!=0)flag=1; else if((i2&(1<<6))!=0&&(i3%2!=0||i4%3!=0))flag=1; else if((i2&(1<<7))!=0&&i6!=0)flag=1; else if((i2&(1<<8))!=0&&i3!=0)flag=1; else if((i2&(1<<9))!=0&&i4!=0)flag=1; if(flag==0)res+=dp[0][i2][i3][i4][i5][i6]; } return res; } int main() { ios_base::sync_with_stdio(0); long long l,r; cin>>l>>r; cout<<calc(r)-calc(l-1)<<endl; }
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 | #include <bits/stdc++.h> using namespace std; long long dp[19][1024][8][9][5][7]; long long calc(long long n) { for(int i1=0;i1<19;i1++)for(int i2=0;i2<1024;i2++)for(int i3=0;i3<8;i3++)for(int i4=0;i4<9;i4++)for(int i5=0;i5<5;i5++)for(int i6=0;i6<7;i6++)dp[i1][i2][i3][i4][i5][i6]=0; int len=0; long long N=n; int d[20]={0}; while(N>0) { d[len]=N%10; N/=10; len++; } if(len==0)return 0; len--; for(int i=1;i<d[len];i++)dp[len][1<<i][i%8][i%9][i%5][i%7]++; len--; long long pref=d[len+1]; int msk=(1<<d[len+1]); for(;len>=0;len--) { for(int i=1;i<=9;i++)dp[len][1<<i][i%8][i%9][i%5][i%7]++; for(int i2=0;i2<1024;i2++)for(int i3=0;i3<8;i3++)for(int i4=0;i4<9;i4++)for(int i5=0;i5<5;i5++)for(int i6=0;i6<7;i6++) { for(int k=1;k<=9;k++) { dp[len][i2|(1<<k)][(10*i3+k)%8][(10*i4+k)%9][(10*i5+k)%5][(10*i6+k)%7]+=dp[len+1][i2][i3][i4][i5][i6]; } // dp[len][msk][pref%8][pref%9][pref%5][pref%7]++; } for(int k=1;k<d[len];k++)dp[len][msk|(1<<k)][(10*pref+k)%8][(10*pref+k)%9][(10*pref+k)%5][(10*pref+k)%7]++; pref=10*pref+d[len]; msk|=(1<<d[len]); } dp[0][msk][pref%8][pref%9][pref%5][pref%7]++; long long res=0; for(int i2=0;i2<1024;i2++)for(int i3=0;i3<8;i3++)for(int i4=0;i4<9;i4++)for(int i5=0;i5<5;i5++)for(int i6=0;i6<7;i6++) { int flag=0; if((i2&(1<<0))!=0)flag=1; else if((i2&(1<<2))!=0&&i3%2!=0)flag=1; else if((i2&(1<<3))!=0&&i4%3!=0)flag=1; else if((i2&(1<<4))!=0&&i3%4!=0)flag=1; else if((i2&(1<<5))!=0&&i5!=0)flag=1; else if((i2&(1<<6))!=0&&(i3%2!=0||i4%3!=0))flag=1; else if((i2&(1<<7))!=0&&i6!=0)flag=1; else if((i2&(1<<8))!=0&&i3!=0)flag=1; else if((i2&(1<<9))!=0&&i4!=0)flag=1; if(flag==0)res+=dp[0][i2][i3][i4][i5][i6]; } return res; } int main() { ios_base::sync_with_stdio(0); long long l,r; cin>>l>>r; cout<<calc(r)-calc(l-1)<<endl; } |