[51nod1232]完美数

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

如果一个数能够被组成它的各个非0数字整除，则称它是完美数。例如：1-9都是完美数，10,11,12,101都是完美数，但是13就不是完美数（因为13不能被数字3整除）。
现在给定正整数x,y，求x和y之间（包含x和y的闭区间）共有多少完美数。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数，X, Y中间用空格分割。(1 <= X <= Y <= 10^18)
Output
输出共T行，对应区间中完美数的数量。

1..10的lcm为2520，从1..10里选若干个数的lcm个数只有四十多个。。

f[i][j][k]表示十进制下长度为i位的数字里，那个数字模2520后的值为j的倍数，数位上各个非0数字的lcm为第k种。

之后就是正常的数位DP了。

一开始不会做是因为状态表示得不对...第二维没有考虑倍数...结果统计的复杂度就上天了...

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 #include<cstdlib>

 #define ll long long

 #define ull unsigned long long

 #define ui unsigned int

 //#define d double

 #define ld long double

 const int maxn=,inf=;

 ll f[][][];

 int NEXT[][],LCM[][],id[],num[];

 int i,j,k,n,m,s,t,ans;

 int ra,fh;char rx;

 inline int read(){

     rx=getchar(),ra=,fh=;

     while(rx<''&&rx!='-')rx=getchar();

     if(rx=='-')fh=-,rx=getchar();

     while(rx>='')ra=ra*+rx-,rx=getchar();return ra*fh;

 }

 inline int gcd(int a,int b){return !b?a:gcd(b,a%b);}

 inline void pre(){

     int i,j,tmp=;

     memset(f,,sizeof(f));

     for(i=;i<=;i++){

         if(!(%i))id[i]=++tmp;

         LCM[i][]=LCM[i][]=i;

         for(j=;j<=;j++)LCM[i][j]=i*j/gcd(i,j);

     }

     for(i=;i<;i++)for(j=;j<=;j++)NEXT[i][j]=(i*+j)%;

 }

 ll dfs(int i,int p,int lcm,bool pr){

     if(i<)return !(p%lcm);

     if(!pr&&f[i][p][id[lcm]]!=-)return f[i][p][id[lcm]];

     int mx=!pr?:num[i];ll tmp=;

     for(int j=;j<=mx;j++)

         tmp+=dfs(i-,NEXT[p][j],LCM[lcm][j],pr&&j==mx);

     if(!pr)f[i][p][id[lcm]]=tmp;

     return tmp;

 }

 inline ll get(ll x){

     int len=;while(x)num[len++]=x%,x/=;

     return dfs(len-,,,);

 }

 int main(){

     pre();ll l,r;

     for(int t=read();t;t--)

         scanf("%lld%lld",&l,&r),

         printf("%lld\n",get(r)-get(l-));

 }