题目链接: http://poj.org/problem?id=2117
题目大意：统计一个范围内数的个数，要求该数能被各位上的数整除。范围2^64。
解题思路：
一开始SB地开了10维数组记录情况。
首先要求能被各位上的数整除，可以转化为被一个数整除问题。
这个数就是各位上数的最小公倍数LCM（不是GCD）。
其次，处理整除问题，得转化成数位DP的余数模板。1~9的LCM最大是2520, 那么%2520,让其可以开数组进行记忆化搜索。
最后, 对于不能%2520最后结果，再%各个数位累计过来的LCM。
这样下来，需要开20*2520*2520的数组，往CF上一交你会发现MLE。
仔细观察每次的LCM，其范围是1~2520没错，但是都是整除gcd的结果（LCM=a*b/gcd(a,b) ），也就是说所有LCM都是某个数的约数。
这个数其实就是2520。所以DP之前，为2520打个表，把LCM给离散化Hash。这样其实只有48个LCM了。数组开20*2520*50即可。
注意结果是int64。
#include "cstdio"
#include "cstring"
using namespace std;
#define LL long long
LL dp[][][],digit[],Hash[];
int gcd(int a,int b) {return b==?a:gcd(b,a%b);}
int lcm(int a,int b) {return a*b/gcd(a,b);}
LL dfs(int len,int Remain,int Lcm,bool fp)
{
if(!len) return Remain%Lcm?:;
printf("%d\n",Lcm);
if(!fp&&dp[len][Remain][Hash[Lcm]]!=-) return dp[len][Remain][Hash[Lcm]];
LL ret=,fpmax=fp?digit[len]:;
for(int i=;i<=fpmax;i++)
ret+=dfs(len-,(Remain*+i)%,i==?Lcm:lcm(Lcm,i),fp&&i==fpmax);
if(!fp) dp[len][Remain][Hash[Lcm]]=ret;
return ret;
}
LL f(long long x)
{
int len=;
while(x)
{
digit[++len]=x%;
x/=;
}
return dfs(len,,,true);
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
LL l,r,cnt=;
scanf("%d",&T);
memset(dp,-,sizeof(dp));
for(int i=;i*i<=;i++)
{
if(%i==)
{
Hash[i]=cnt++;
if(i*i!=) Hash[/i]=cnt++;
}
}
while(T--)
{
scanf("%I64d%I64d",&l,&r);
LL res=f(r)-f(l-);
printf("%I64d\n",res);
}
}
| 2908091(#) | neopenx | CodeForces | 55D | Accepted | 19800 | 780 | GNU C++ 4.6 | 1121 |
2014-10-30 19:41:38
|