涉及知识点：数位DP
题意
令 \(\text{dig}(i)\) 表示 \(i\) 十进制表示下各数位乘积，则一个数对是正确的当且仅当满足以下条件：
- \(1 \leq i,j \leq n\)
- \(\text{dig}(i) \times \text{dig}(j) > 0\)
- \(\gcd(\text{dig}(i), \text{dig}(j)) \leq k\)
给你 \(n,k\ (\leq 10^{18})\) 求有多少正确的有序数对。答案对 \(998244353\) 取模。
思路
由于 \(\text{dig}\) 为“数位”的乘积，我们知道一个 \(1\leq x\leq 9\) 的数的质因子只有可能为 \(2,3,5,7\)，因此乘起来质因子也只有这四个，而且发现这四个质因子个数的有效组合其实只有 \(10^4\) 级别。
记 \(f_{i,j,k,l}\) 为满足 \(2^i \times 3^j \times 5^k \times 7^l | \text{dig}(a)\) 且满足 \(a\leq n\) 的 \(a\) 的个数。这东西可以数位 DP。
那么满足 \(\gcd(\text{dig}(a),\text{dig}(b))=2^i \times 3^j \times 5^k \times 7^l\) 的 \((a,b)\) 有序数对的个数为：
\[\large\sum\limits_{p_1, p_2, p_3, p_4 \in {0,1}} f_{i+p_1,j+p_2,k+p_3,l+p_4}^2 \times (-1)^{p_1 + p_2 + p_3 + p_4} \]这是个容斥式，\(f_{i,j,k,l}\) 意味着 \(x=2^{x_2} \times 3^{x_3} \times 5^{x_5} \times 7^{x_7}(x_2\geq i,x_3\geq j,x_5\geq k,x_7\geq l),x\leq n\) 的情况数。
设 \(a=2^{a_2} \times 3^{a_3} \times 5^{a_5} \times 7^{a_7}, b=2^{b_2} \times 3^{b_3} \times 5^{b_5} \times 7^{b_7}\) 时，我们通过上述容斥式算出了 \(\min(a_2,b_2)=i,\min(a_3,b_3)=j,\min(a_5,b_5)=k,\min(a_7,b_7)=l\) 的情况数。具体做法可以理解为用 \(f_{i,j,k,l}\) 减去了 \((i+1,j,k,l),(i,j+1,k,l),(i,j,k+1,l),(i,j,k,l+1)\) 这几种情况的并集（也就是 \(a,b\) 存在质因子对应的指数取 \(\min\) 大于我们想要的情况）。
我们又知道 \(\gcd(a,b)=2^{\min(a_2,b_2)} \times 3^{\min(a_3,b_3)} \times 5^{\min(a_5,b_5)} \times 7^{\min(a_7,b_7)}\)，因此就算出来了满足 \(\gcd(\text{dig}(a),\text{dig}(b))=2^i \times 3^j \times 5^k \times 7^l\) 的 \((a,b)\) 有序数对的个数。
最后遍历一下质因子之积 \(\leq k\) 的所有组合统计答案即可。
标签：gcd,GCD,min,text,dig,times,leq,NFLS,NOI From： https://www.cnblogs.com/SkyNet-PKN/p/18211336