前置知识
解法
同余的传递性:若 \(\begin{cases} a,b \in \mathbf{Z} \\ p,q \in \mathbb{N}^{*} \\ q|p \end{cases}\) ,则当 \(a \equiv b \pmod{p}\) 时有 \(a \equiv b \pmod{q}\)。故在本题中 \(\bmod\) 各非零数码均等于 \(0\) 等价于 \(\bmod\) 各非零数码的 \(\operatorname{lcm}\) 等于 \(0\),等价于 \(\mod 2520\) 后的结果 \(\bmod\) 各非零数码的 \(\operatorname{lcm}\) 等于 \(0\)。
同时,对于 \(S \subset \{1,2,3,4,5,6,7,8,9 \}\),有 \(\operatorname{lcm}\limits_{x \in S} \{ x \}|2520\)。
所以我们可以预处理出 \(2520\) 的因数并离散化,分别记录当前位置、所构成的数字 \(\mod 2520\) 后的结果、非零数码的 \(\operatorname{lcm}\), 接着就和正常的数位 DP 一样了。
注意搜索顺序对答案继承的影响。
另外,本题限制代码长度 \(<1kB\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll a[25],g[2600],f[25][2600][55];
ll lcm(ll a,ll b)
{
return a/__gcd(a,b)*b;
}
ll divide(ll n,ll a[])
{
ll len=0;
while(n)
{
len++;
a[len]=n%10;
n/=10;
}
return len;
}
ll dfs(ll pos,ll pre_sum,ll pre_lcm,ll limit,ll p)
{
if(pos<=0)
{
return (pre_sum%pre_lcm==0);
}
if(f[pos][pre_sum][g[pre_lcm]]!=-1&&limit==0)
{
return f[pos][pre_sum][g[pre_lcm]];
}
ll ans=0,maxx=(limit==0)?9:a[pos],i;
for(i=0;i<=maxx;i++)
{
ans+=dfs(pos-1,(pre_sum*10%p+i)%p,(i==0)?pre_lcm:lcm(pre_lcm,i),(i==maxx)*limit,p);
}
return (limit==0)?f[pos][pre_sum][g[pre_lcm]]=ans:ans;
}
ll ask(ll n)
{
ll len=divide(n,a);
return dfs(len,0,1,1,2520);
}
void init()
{
ll num=0;
memset(f,-1,sizeof(f));
for(ll i=1;i<=2520;i++)
{
if(2520%i==0)
{
num++;
g[i]=num;
}
}
}
int main()
{
ll t,l,r,i;
cin>>t;
init();
for(i=1;i<=t;i++)
{
cin>>l>>r;
cout<<ask(r)-ask(l-1)<<endl;
}
return 0;
}
后记
多倍经验: CF55D Beautiful numbers
标签:Beautiful,2520,题解,ll,SP8177,len,数码,lcm,operatorname From: https://www.cnblogs.com/The-Shadow-Dragon/p/18280392