首页 > 代码库 > Codeforces 55D Beautiful numbers(数位dp)
Codeforces 55D Beautiful numbers(数位dp)
题目大意：T(<=10)组数据，求[a,b]能够被其每个数位的数都整除的数(a,b<=9*10^18)
这题差一点就想出来了，可是最后一步好难想也好妙啊
首先这个数能够整除各个数位的lcm，而最大的lcm为2520(5*7*8*9)。我的想法是枚举lcm（记为lcmm），求出各个数位的lcm为lcmm且这个数能整除lcm的数有多少，dp[pos][val][lcm][lcmm]表示枚举lcmm，前pos位，这个数%lcmm为val，各个数位的lcm，然后实际上lcmm和lcm只有50个，所以后两维离散化就从2520->50了。但是我突然眉头一皱发现事情并不简单，pos最大为20，val最大为2520，lcm最大为50，lcmm最大为50,20*2520*50*50=126000000... QAQ滚去看题解
设这个数为a，各数位为ai，lcm(ai)|a，lcm(ai)|2520，所以lcm(ai)|(a%2520)。这个怎么证呢？其实很简单。
设lcm(ai)x=a，lcm(ai)y=2520，则(a%2520)=lcm(ai)x-lcm(ai)y*z=lcm(ai)(x-y*z)，还是含有lcm(ai)。也就是说并不需要枚举lcmm，只要边dp边把val%2520就可以了...省了一维50，于是就巧妙的过了。
代码如下：
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #define ll long long using namespace std; ll dp[20][2550][50],a[20],l,r,num[2550],cnt,T; void read(ll &k) { k=0;ll f=1;char c=getchar(); while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar(); while(c<=‘9‘&&c>=‘0‘)k=k*10+c-‘0‘,c=getchar(); k*=f; } ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll dfs(int pos,int val,int lcm,bool limit) { if(pos==0)return val%lcm==0; if(!limit && dp[pos][val][num[lcm]]!=-1)return dp[pos][val][num[lcm]]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i<=up;i++) ans+=dfs(pos-1,(val*10+i)%2520,i?(ll)lcm*i/gcd(lcm,i):lcm,limit && i==a[pos]); if(!limit)dp[pos][val][num[lcm]]=ans; return ans; } ll solve(ll x) { if(x==-1)return 0; int pos=0; while(x) { a[++pos]=x%10; x/=10; } ll ans=0; ans+=dfs(pos,0,1,1); return ans; } int main() { for(int i=1;i<=2520;i++) if(!(2520%i))num[i]=++cnt; memset(dp,-1,sizeof(dp)); read(T); while(T--)read(l),read(r),printf("%lld\n",solve(r)-solve(l-1)); }
Codeforces 55D Beautiful numbers(数位dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。