[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-));
}
上一篇:React 生命周期介绍


下一篇:ASP.NET Core DI 手动获取注入对象