digit-product：各个数位的乘积
self-product：digit-product与自身的乘积
首先我们可以发现一个数的digital-product小于等于其本身，所以一个数的digit-product<=根号下self-product
在这题的数据范围下就<=1e9，而digit-product的质因数只可能有2,3,5,7，1e9内质因数只有2,3,5,7的数非常少，那么我们枚举digit-product，设为p，每次求出在l/p上取整到r/p下取整之间digit-product等于p的数即可，也就是2,3,5,7的次数与p中2,3,5,7的次数相等，这个可以数位dp搞定
#include<iostream> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<cstdlib> #include<cstdio> #include<map> #include<bitset> #include<set> #include<stack> #include<vector> #include<queue> using namespace std; #define MAXN 1010 #define MAXM 1010 #define ll long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 ll ans; ll f[19][10][30][19][13][11]; int p[10][4]={{0,0,0,0},{0,0,0,0},{1,0,0,0},{0,1,0,0},{2,0,0,0},{0,0,1,0},{1,1,0,0},{0,0,0,1},{3,0,0,0},{0,2,0,0}}; ll mi[20]; ll cal(int l1,int l2,int l3,int l4,ll n,ll P){ if(n==0){ return 0; } int i,j; int len; ll re=0; for(len=1;len<=18;len++){ if(mi[len]>n){ break; } } len--; for(i=1;i<len;i++){ for(j=1;j<=9;j++){ re+=f[i][j][l1][l2][l3][l4]; } } int y=n/mi[len]; for(i=1;i<y;i++){ re+=f[len][i][l1][l2][l3][l4]; } l1-=p[y][0]; l2-=p[y][1]; l3-=p[y][2]; l4-=p[y][3]; if(l1>=0&&l2>=0&&l3>=0&&l4>=0){ for(i=len-1;i;i--){ int y=n/mi[i]; if(!y){ break; } for(j=1;j<y;j++){ re+=f[i][j][l1][l2][l3][l4]; } l1-=p[y][0]; l2-=p[y][1]; l3-=p[y][2]; l4-=p[y][3]; if(l1<0||l2<0||l3<0||l4<0){ break; } } } ll t=1; for(i=len;i;i--){ t*=n/mi[i]; } re+=t==P; return re; } int main(){ int i,j,k,l; ll a,b,c,d; ll L,R; f[0][1][0][0][0][0]=1; mi[1]=1; for(i=2;i<=18;i++){ mi[i]=mi[i-1]*10; } ll x,y,z; for(x=0;x<18;x++){ for(i=0,a=1;a<=INF;i++,a*=2){ for(j=0,b=1;a*b<=INF;j++,b*=3){ for(k=0,c=1;a*b*c<=INF;k++,c*=5){ for(l=0,d=1;a*b*c*d<=INF;l++,d*=7){ for(y=1;y<=9&&a*b*c*d*y<=INF;y++){ for(z=1;z<=9;z++){ if(i+p[y][0]<30&&j+p[y][1]<19&&k+p[y][2]<13&&l+p[y][3]<11){ f[x+1][y][i+p[y][0]][j+p[y][1]][k+p[y][2]][l+p[y][3]]+=f[x][z][i][j][k][l]; } } } } } } } } scanf("%lld%lld",&L,&R); for(i=0,a=1;a<=INF;i++,a*=2){ for(j=0,b=1;a*b<=INF;j++,b*=3){ for(k=0,c=1;a*b*c<=INF;k++,c*=5){ for(l=0,d=1;a*b*c*d<=INF;l++,d*=7){ ll p=a*b*c*d; ans+=cal(i,j,k,l,R/p,p); ans-=cal(i,j,k,l,(L+p-1)/p-1,p); } } } } printf("%lld\n",ans); return 0; } /* 1 10 */
