DTOJ#5076. 恋人·米路缇欧

题目背景

想成为「连理」的共犯呢，属于我的你。

联系起「奇遇」吧，我是《恋人》，掌管《诱惑》。

就算离「月意」而去，多少新伴侣我都能帮你找来。

展现那「染着」吧。你渴望什么颜色的爱呢?

题目描述

恋人要解开魔法阵以葬送自己的同伴，然后复生亡者。而解开魔法阵需要密码。

密码是一种正整数有序数对 $(i,j)$，令 $dig(i)$ 表示 $i$ 十进制表示下各数位乘积，则一个数对是正确的当且仅当满足以下条件：

• $0<i,j\le n$
• $dig(i)\times dig(j)>0$
• $\gcd (dig(i),dig(j))\le k$

其中 $\gcd (x,y)$ 表示正整数 $x,y$ 的最大公约数。

现在恋人想知道有多少满足要求的数对。由于解锁魔法阵不需要过多的数对，你只需要输出答案对 $998244353$ 取模的值。

输入一行两个正整数 $n,k$。

输出一行一个数，表示答案对 $998244353$ 取模的值。

样例输入 1

9 5

样例输出 1

77

样例解释 1

除 $(6,6),(7,7),(8,8),(9,9)$ 外，其余满足 $0<i,j\le 9$ 的正整数有序数对 $(i,j)$ 都满足 $dig(i)\times dig(j)>0$ 与 $\gcd (dig(i),dig(j))\le 5$。

样例输入 2

7 7

样例输出2

49

对于 $50\%$ 的数据，n≤106n \leq 10^6n≤106；

对于 $100\%$ 的数据，0<n,k≤10180 < n, k \leq 10^{18}0<n,k≤1018。

成都七中 csp2020 模拟2

因为质因数只有 2，3，5，7，所以直接$f[i][j][k][h][t]$记录四个选择的状态，同时套数位DP。
计算答案时枚举gcd，通过后缀和容斥计算。

注意：101810^{18}1018有 19 位。。

#include<bits/stdc++.h>
#define N 20
typedef long long ll;
using namespace std;
const int mod=998244353;
inline ll read(){ll x=0,f=1;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}return x*f;
}
int f[61][41][21][21],tmp[70][70][70][70];//d 2 3 5 7
//          0 1 2 3 4 5 6 7 8 9
int d2[10]={0,0,1,0,2,0,1,0,3,0};
int d3[10]={0,0,0,1,0,0,1,0,0,2};
int d5[10]={0,0,0,0,0,1,0,0,0,0};
int d7[10]={0,0,0,0,0,0,0,1,0,0};
int top,w[N],ma2,ma3,ma5,ma7;
ll p2[70],p3[50],p5[22],p7[22];
inline void add(int &a,int b){a=(a+b)%mod;
}
inline void work(ll n){top=0;while(n){w[++top]=n%10;n/=10;}
//	for(int i=top;i;--i)cout<<w[i];cout<<endl;
//	cout<<top<<endl;int n2=0,n3=0,n5=0,n7=0,fl=min(top,1);for(int i=top;i;--i){memset(tmp,0,sizeof(tmp));for(int j=1;j<=9;++j){for(int k2=0;k2<=ma2;++k2){for(int k3=0;k3<=ma3;++k3){for(int k5=0;k5<=ma5;++k5){for(int k7=0;k7<=ma7;++k7){add(tmp[k2+d2[j]][k3+d3[j]][k5+d5[j]][k7+d7[j]],f[k2][k3][k5][k7]);}}}}}ma2+=3,ma3+=2,ma5+=1,ma7+=1;if(fl){for(int j=1;j<w[i];++j){add(tmp[n2+d2[j]][n3+d3[j]][n5+d5[j]][n7+d7[j]],1);}if(w[i]==0)fl=0;n2+=d2[w[i]],n3+=d3[w[i]],n5+=d5[w[i]],n7+=d7[w[i]];}if(i!=top){for(int j=1;j<=9;++j){add(tmp[d2[j]][d3[j]][d5[j]][d7[j]],1);}}for(int k2=0;k2<=ma2;++k2)for(int k3=0;k3<=ma3;++k3)for(int k5=0;k5<=ma5;++k5)for(int k7=0;k7<=ma7;++k7)f[k2][k3][k5][k7]=tmp[k2][k3][k5][k7];}add(f[n2][n3][n5][n7],fl);p2[0]=p3[0]=p5[0]=p7[0]=1;
//	cout<<ma2<<" "<<ma3<<" "<<ma5<<" "<<ma7<<endl;for(int i=1;i<=ma2;++i)p2[i]=p2[i-1]*1ll*2;for(int i=1;i<=ma3;++i)p3[i]=p3[i-1]*1ll*3;for(int i=1;i<=ma5;++i)p5[i]=p5[i-1]*1ll*5;for(int i=1;i<=ma7;++i)p7[i]=p7[i-1]*1ll*7;
}
int g[70][70][70][70],sg[70][70][70][70],s2=1,s3=2,s5=4,s7=8;
int x[5]={-1,1,-1,1,-1};
int main(){
//	freopen("data.in","r",stdin);
//	freopen("test.out","w",stdout);ll n=read(),k=read();//cout<<n<<" "<<k<<endl;//if(n==1e18)n--;work(n);int ans=0;for(int i2=ma2;i2>=0;--i2){for(int i3=ma3;i3>=0;--i3){for(int i5=ma5;i5>=0;--i5){for(int i7=ma7;i7>=0;--i7){for(int s=1;s<16;++s){int t2=i2,t3=i3,t5=i5,t7=i7;if(s&s2)++t2;if(s&s3)++t3;if(s&s5)++t5;if(s&s7)++t7;int val=1ll*x[t2+t3+t5+t7-i2-i3-i5-i7]*f[t2][t3][t5][t7]%mod;add(f[i2][i3][i5][i7],val);val=1ll*x[t2+t3+t5+t7-i2-i3-i5-i7]*sg[t2][t3][t5][t7]%mod;add(g[i2][i3][i5][i7],-val);}sg[i2][i3][i5][i7]=1ll*f[i2][i3][i5][i7]*f[i2][i3][i5][i7]%mod;add(g[i2][i3][i5][i7],sg[i2][i3][i5][i7]);}}}}ll v2,v3,v5,v7;for(int i2=0;i2<=ma2;++i2){v2=p2[i2];if(v2>k)break;for(int i3=0;i3<=ma3;++i3){v3=p3[i3];if(v2*v3>k)break;for(int i5=0;i5<=ma5;++i5){v5=p5[i5];if(v2*v3*v5>k)break;for(int i7=0;i7<=ma7;++i7){v7=p7[i7];if(v2*v3*v5*v7>k)break;//  cout<<v2<<" "<<v3<<" "<<v5<<" "<<v7<<" "<<v2*v3*v5*v7<<endl;add(ans,g[i2][i3][i5][i7]);}}}}//for(long long i=0;i<=ma7;++i)cout<<p7[i]<<" ";cout<<endl;printf("%d\n",(ans+mod)%mod);//ll y=e18;//cout<<y<<endl;
//	cout<<k<<endl;return 0;
}
/*
1000000000000000000 10
*/