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 }
时间: 04-17

51nod 1232:完美数的相关文章

51nod 1232 完美数 数位dp

1232 完美数 题目来源: 胡仁东 基准时间限制:2 秒 空间限制:131072 KB 如果一个数能够被组成它的各个非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中间用空

ACdream 1064 完美数

完美数 Time Limit: 2000/1000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others) SubmitStatisticNext Problem Problem Description 8是中国人很喜欢的一个数字,但是如果有3的存在就变成了38,就不是很好了.. 你能告诉我,在[L, R] 的正整数区间内,要么包含3 要么包含 8 的不同的整数有多少个么? Input 第一行一个整数T (T ≤ 10000),代表数据

完美数(打表)

                     完美数                        Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Description 任何一个自然数的约数中都有1和它本身,我们把小于它本身的因数叫做这个自然数的真约数. 如6的所有真约数是1.2.3,而且6=1+2+3.像这样,一个数所有真约数的和正好等于这个数,通常把这个数叫做完美数. 古希腊人非常重视完美数.

HNU 12876 Quite Good Numbers 完美数变形

筛法是一种很快的方法,贴代码纪念一下. 做法很像筛法 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <

51NOD 1623 完美消除 数位DP

题目描述: 定义数的消除操作为选定[L,R,x],如果数的第L到第R位上的数字都大于等于x,并且这些数都相等,那么该操作是合法的(从低位到高位编号,个位是第一位,百位是第二位……),然后将这些位数上的数减x:否则就是不合法的,不能进行操作.对一个数操作最少的次数使得这个数变成0,这个操作次数称为该数的最小操作数.如:1232的最小操作数为3,一个合法解是[2,2,1],[1,3,2],[4,4,1]. 求L~R中最小操作数为k的数的个数. 例如:132,需要操作3次才能变为0.而131131 =

51nod 1412 AVL数的种类(DP

题意给了n个节点的AVL数 问种类 树的深度不大 那么转移方程很明显了 dp[i][j]   代表的是节点为n深度为j的树的种类 k为左子树的节点个数 //dp[i][j+1] += dp[k][j]*dp[i-k-1][j];//dp[i][j+1] += 2*dp[k][j-1]*dp[i-k-1][j]; #include <stdio.h> #include <iostream> #include <algorithm> #include <string.

51nod 矩阵取数

一个N*N矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,从左上走到右下,只能向下向右走,求能够获得的最大价值.例如:3 * 3的方格. 1 3 32 1 32 2 1 能够获得的最大价值为:11. 简单DP  维护最大和  dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]; AC代码: #include<bits/stdc++.h>using namespace std;int n;//const int inf=1<<29;in

数位计数问题

在信息学竞赛中,有一类难度不大但异常麻烦的问题--数位计数问题, 这类问题的主要特点是询问的答案和一段连续的数的各个数位相关,并且需要对时间效率有一定要求. 由于解决这类问题往往意味着巨大的代码量,而众多的特 殊情况又意味着出现错误的巨大可能性,因此很少有人愿意解决此类问题, 但只要掌握好的方法,解决这类问题也并非想象中的那样困难------<<数位计数问题解法研究>>高逸涵. 其实数位DP或者说数位计数问题没这么难,只要构造出合适的状态,就能解决. 动态规划的核心就是在于状态的设

【分块打表】bzoj 3758 数数

[题目描述] Description 神犇最近闲来无事,于是就思考哲学,研究数字之美.在神犇看来,如果一个数的各位能够被分成两个集合,而且这两个集合里的数的和相等,那么这个数就是优美的(具体原因就只有神犇才知道了).现在神犇在思考另一个问题,在区间[a,b]中有多少个数是优美的?这个问题对于神犇来说很简单,相信对于你来说也不难. Input 输入只有一行,包含两个整数a和b. Output 输出只有一行,包含一个整数,代表区间[a,b]中优美的数的个数. Sample Input 1 11 Sa

杭电ACM分类

杭电ACM分类: 1001 整数求和 水题1002 C语言实验题——两个数比较 水题1003 1.2.3.4.5... 简单题1004 渊子赛马 排序+贪心的方法归并1005 Hero In Maze 广度搜索1006 Redraiment猜想 数论:容斥定理1007 童年生活二三事 递推题1008 University 简单hash1009 目标柏林 简单模拟题1010 Rails 模拟题(堆栈)1011 Box of Bricks 简单题1012 IMMEDIATE DECODABILITY