首页 > 代码库 > 51nod 1232：完美数
51nod 1232：完美数
51nod 1232：完美数
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1232
题目大意：如果一个数能够被组成它的各个非$0$数字整除，则称它是完美数。例如：$10$,$11$,$12$,$101$都是完美数，但是$13$就不是完美数（因为$13$不能被数字3整除）。现在给定正整数$x$,$y$，求$[x,y]$中共有多少完美数。共有$T$组数据。
数位DP
如果对于$a \equiv r(mod m)$，存在$p|m$，则有$a \equiv r(mod p)$.
故我们可以记录被$2520$（$lcm(1,2,3,4,5,6,7,8,9)$）模的余，代替分别记录被$1,2,3,4,5,6,7,8,9$模的余.
而标识$n$中含哪些数有多种方法：可以记录$lcm(p_i)$（此种需将$2520$的因子离散化），也可以用多个bool类型标记.
由于这道题$T$过大，故递推的方法不可行，采用记忆化搜索.
代码如下：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #define N 20 6 using namespace std; 7 typedef long long ll; 8 const int m=2520; 9 int T,dig[N];10 ll a,b,dp[N][50][2520],f[2525],g[50],mod[20];11 int gcd(int a,int b){12 return b==0?a:gcd(b,a%b);13 }14 int lcm(int a,int b){15 return a/gcd(a,b)*b;16 }17 ll dfs(int pos,int fact,int r,bool limit){18 if (pos<0) return r%g[fact]==0;19 if (!limit&&dp[pos][fact][r]!=-1) return dp[pos][fact][r];20 ll res=0;21 int last=limit?dig[pos]:9;22 for (int i=0;i<=last;i++){23 int x=g[fact];24 if(i>1)x=lcm(x,i);25 res+=dfs(pos-1,f[x],(r+mod[pos]*i)%m,limit&&(i==last));26 }27 if (!limit) dp[pos][fact][r]=res;28 return res;29 }30 ll solve(ll n){31 int len=0;32 while (n){33 dig[len++]=n%10;34 n/=10;35 }36 return dfs(len-1,0,0,1);37 }38 void init(){39 int k=0,i;40 memset(dp,-1,sizeof(dp));41 for(i=1;i*i<m;++i)if(m%i==0){42 g[k++]=i;43 g[k++]=m/i;44 }45 if(i*i==m)g[k++]=i;46 sort(g,g+k);47 for(int i=0;i<k;++i)f[g[i]]=i;48 for(int i=0,t=1;i<=18;++i,t=(t*10)%m)mod[i]=t;49 }50 int main(void){51 init();52 scanf("%d",&T);53 while(T--){54 scanf("%lld%lld",&a,&b);55 printf("%lld\n",solve(b)-solve(a-1));56 }57 }
51nod 1232：完美数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。