题目大意：
LOVER解开魔法阵需要密码。密码是一种正整数有序数对(i, j)，令dig (i) 表示i 十进制表示下各数位乘积，则一个数对是正确的当且仅当满足以下条件：• 0 < i, j ≤ n；• dig (i) × dig (j) > 0；• gcd (dig (i) , dig (j)) ≤ k。其中gcd (x, y) 表示正整数x, y 的最大公约数。现在恋人想知道有多少满足要求的数对。由于解锁魔法阵不需要过多的数对，你只需要输出答案对998244353 取模的值。
这是一道考场时很多大佬切了，但我不会做的题。
做法不难，主要分为三个步骤：
- 首先，很容易可以发现，对gcd有贡献的只有2,3,5,7，所以可以设dp数组f[i][0/1][a][b][c][d]表示当前选到从后往前第i位，当前2,3,5,7的数量为a,b,c,d的数的个数，0表示没有限制的情况，1表示小于等于到i的限制的情况。
- 求出了这个以后，就可以用高维前缀和求出数组sum[a][b][c][d]表示当前当前2,3,5,7的数量>=a,b,c,d时的数的个数。
- 最后，就可以枚举一种符合答案的(a,b,c,d)。设数对为（i,j）,分类讨论i控制某几个点和j控制某几个点的情况，共16种，复制粘贴即可。
有一点细节要注意：如果直接确定i,j可以取得（a,b,c,d）的范围，会算重复。比如当i控制a,b,c,d的最小值，或者j控制a,b,c,d的最小值时，i和j都可以选(a,b,c,d),这样显然是有问题的。
经过roger大佬的帮助，我学会了一种方法：考虑i的范围时，令其不能与j重复，j则可以重复，这样就不会算重了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 20
#define ll long long
#define mo 998244353
using namespace std;
ll n,k,i,j,a,b,c,d,len,lim[N],f[N][3][N*3][N*2][N][N],g[N*3][N*2][N][N],sum[N*3][N*2][N][N],ans,a1,b1,c1,d1;
ll check(ll a,ll b,ll c,ll d,ll k){
ll i,sum=1;
for (i=1;i<=a;i++) sum*=2;
for (i=1;i<=b;i++) sum*=3;
for (i=1;i<=c;i++) sum*=5;
for (i=1;i<=d;i++) sum*=7;
if (sum<=k) return 1;
return 0;
}
ll get(ll al,ll ar,ll bl,ll br,ll cl,ll cr,ll dl,ll dr){
ar++;br++;cr++;dr++;
ll res=sum[al][bl][cl][dl];
res=res-sum[ar][bl][cl][dl]-sum[al][br][cl][dl]-sum[al][bl][cr][dl]-sum[al][bl][cl][dr];res=(res+mo)%mo;
res=res+sum[ar][br][cl][dl]+sum[ar][bl][cr][dl]+sum[ar][bl][cl][dr]
+sum[al][br][cr][dl]+sum[al][br][cl][dr]+sum[al][bl][cr][dr];res%=mo;
res=res-sum[ar][br][cr][dl]-sum[ar][br][cl][dr]-sum[ar][bl][cr][dr]-sum[al][br][cr][dr];res=(res+mo)%mo;
res=res+sum[ar][br][cr][dr];res%=mo;
return res;
}
int main(){
freopen("lover.in","r",stdin);
freopen("lover.out","w",stdout);
scanf("%lld%lld",&n,&k);
f[0][0][0][0][0][0]=f[0][1][0][0][0][0]=1;
while (n){
lim[++len]=n%10;
n/=10;
}
for (i=0;i<len;i++){
for (a=0;a<=i*3;a++)
for (b=0;b<=i*2;b++)
for (c=0;c<=i;c++)
for (d=0;d<=i;d++)
if (f[i][0][a][b][c][d]||f[i][1][a][b][c][d])
for (j=1;j<=9;j++){
a1=b1=c1=d1=0;
if (j==2) a1++;else
if (j==3) b1++;else
if (j==4) a1+=2;else
if (j==5) c1++;else
if (j==6) a1++,b1++;else
if (j==7) d1++;else
if (j==8) a1+=3;else
if (j==9) b1+=2;
f[i+1][0][a+a1][b+b1][c+c1][d+d1]=(f[i+1][0][a+a1][b+b1][c+c1][d+d1]+f[i][0][a][b][c][d])%mo;
if (j<lim[i+1]) f[i+1][1][a+a1][b+b1][c+c1][d+d1]=(f[i+1][1][a+a1][b+b1][c+c1][d+d1]+f[i][0][a][b][c][d])%mo;
if (j==lim[i+1]) f[i+1][1][a+a1][b+b1][c+c1][d+d1]=(f[i+1][1][a+a1][b+b1][c+c1][d+d1]+f[i][1][a][b][c][d]);
}
}
for (i=1;i<=len;i++)
for (a=0;a<=i*3;a++)
for (b=0;b<=i*2;b++)
for (c=0;c<=i;c++)
for (d=0;d<=i;d++){
if (i<len)
sum[a][b][c][d]=g[a][b][c][d]=(g[a][b][c][d]+f[i][0][a][b][c][d])%mo;
else
sum[a][b][c][d]=g[a][b][c][d]=(g[a][b][c][d]+f[i][1][a][b][c][d])%mo;
}
for (a=len*3;a>=0;a--)
for (b=len*2;b>=0;b--)
for (c=len;c>=0;c--)
for (d=len;d>=0;d--)
sum[a][b][c][d]=(sum[a][b][c][d]+sum[a+1][b][c][d])%mo;
for (a=len*3;a>=0;a--)
for (b=len*2;b>=0;b--)
for (c=len;c>=0;c--)
for (d=len;d>=0;d--)
sum[a][b][c][d]=(sum[a][b][c][d]+sum[a][b+1][c][d])%mo;
for (a=len*3;a>=0;a--)
for (b=len*2;b>=0;b--)
for (c=len;c>=0;c--)
for (d=len;d>=0;d--)
sum[a][b][c][d]=(sum[a][b][c][d]+sum[a][b][c+1][d])%mo;
for (a=len*3;a>=0;a--)
for (b=len*2;b>=0;b--)
for (c=len;c>=0;c--)
for (d=len;d>=0;d--)
sum[a][b][c][d]=(sum[a][b][c][d]+sum[a][b][c][d+1])%mo;
ans=0;
for (a=0;a<=len*3;a++)
for (b=0;b<=len*2;b++)
for (c=0;c<=len;c++)
for (d=0;d<=len;d++)
if (check(a,b,c,d,k)){
ans=(ans+get(a+1,len*3,b+1,len*2,c+1,len,d+1,len)*g[a][b][c][d]%mo)%mo;
ans=(ans+get(a,a,b+1,len*2,c+1,len,d+1,len)*get(a,len*3,b,b,c,c,d,d)%mo)%mo;
ans=(ans+get(a+1,len*3,b,b,c+1,len,d+1,len)*get(a,a,b,len*2,c,c,d,d)%mo)%mo;
ans=(ans+get(a+1,len*3,b+1,len*2,c,c,d+1,len)*get(a,a,b,b,c,len,d,d)%mo)%mo;
ans=(ans+get(a+1,len*3,b+1,len*2,c+1,len,d,d)*get(a,a,b,b,c,c,d,len)%mo)%mo;
ans=(ans+get(a,a,b,b,c+1,len,d+1,len)*get(a,len*3,b,len*2,c,c,d,d)%mo)%mo;
ans=(ans+get(a,a,b+1,len*2,c,c,d+1,len)*get(a,len*3,b,b,c,len,d,d)%mo)%mo;
ans=(ans+get(a,a,b+1,len*2,c+1,len,d,d)*get(a,len*3,b,b,c,c,d,len)%mo)%mo;
ans=(ans+get(a+1,len*3,b,b,c,c,d+1,len)*get(a,a,b,len*2,c,len,d,d)%mo)%mo;
ans=(ans+get(a+1,len*3,b,b,c+1,len,d,d)*get(a,a,b,len*2,c,c,d,len)%mo)%mo;
ans=(ans+get(a+1,len*3,b+1,len*2,c,c,d,d)*get(a,a,b,b,c,len,d,len)%mo)%mo;
ans=(ans+get(a,a,b,b,c,c,d+1,len)*get(a,len*3,b,len*2,c,len,d,d)%mo)%mo;
ans=(ans+get(a,a,b,b,c+1,len,d,d)*get(a,len*3,b,len*2,c,c,d,len)%mo)%mo;
ans=(ans+get(a,a,b+1,len*2,c,c,d,d)*get(a,len*3,b,b,c,len,d,len)%mo)%mo;
ans=(ans+get(a+1,len*3,b,b,c,c,d,d)*get(a,a,b,len*2,c,len,d,len)%mo)%mo;
ans=(ans+g[a][b][c][d]*get(a,len*3,b,len*2,c,len,d,len));
}
printf("%lld
",ans);
return 0;
}