正文

51nod1232：完美数

barriery  barriery  2022-08-28  202

关键词：

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
",solve(b)-solve(a-1));
56     }
57 }

51nod1232完美数数位dp

1232 完美数题目来源：胡仁东基准时间限制：2 秒空间限制：131072 KB 如果一个数能够被组成它的各个非0数字整除，则称它是完美数。例如：1-9都是完美数，10,11,12,101都是完美数，但是13就不是完美数（因... 查看详情

51nod1232完美数

题目思路：数位dp，若这个数能被每位的非0数整除，那么这个数一定可以被每一位数的lcm整除，lcm（1,2,3,4,5,6,7,8,9）=2520，所以可以通过将这个数对2520取模来压缩空间,取模结果计做moddp[pos][lcm][mod]，显然20*2520*2520仍然过大，所以... 查看详情

51nod1780完美序列

...每个数出现的次数num[i]。　　然后我们很容易发现，一个完美序列，去掉所有权值大于某个值的数之后，还是完美的。　　这样我们就考虑一路dp过去，将每一种数插进去。然后发现，当前数的决策之和上一个数有关。我们插的... 查看详情

51nod1623完美消除（数位dp）

　　首先考虑一下给一个数如何求它需要多少次操作。　　显然用一个单调栈就可以完成：塞入栈中，将比它大的所有数都弹出，如果栈中没有当前数，答案+1。　　因为数的范围只有0~9，所以我们可以用一个二进制数来模拟这... 查看详情

动态规划51nod1780完美序列(代码片段)

...相邻两项差的绝对值小于等于1，那么我们说这个序列是完美的。给出一个有序数列A，求有多少种完美序列排序后和数列A相同。Input第一行一个数n（<=30000）表示完美序列的长度第二行n个数，表示数列A（每个数<=10^9，每个数... 查看详情

51nod1182完美字符串

1182 完美字符串题目来源： Facebook Hacker Cup选拔基准时间限制：1 秒空间限制：131072 KB分值: 5 难度：1级算法题约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度... 查看详情

51nod1182完美字符串

Input示例dadOutput示例77 #include"bits/stdc++.h"usingnamespacestd;#defineLLlonglong#defineINF0x3f3f3f3f3f#definePIacos(-1)#defineN10010#defineMOD10usingnamespacestd;charstr[N];map<char,int&g 查看详情

51nod1182完美字符串（贪心）

约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配，不同字母的完美度不同，分别对应一个1-26之间的整数。约翰不在乎字母大小写。（也就是说字母F和f）的完美度相同。给定一个字... 查看详情

51nod1182完美字符串字符串排序+哈希

1182 完美字符串题目来源： Facebook Hacker Cup选拔基准时间限制：1 秒空间限制：131072 KB分值: 5 难度：1级算法题收藏关注约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母... 查看详情

51nod1313完美串

...成的字符串，其中0<=L<=R<N。称一个字符串为“完美串”，当且仅当该串中存在K个连续的‘G‘字符。问，存在多少个不同的四元组(a,b,c,d)满查看详情

51nod1230：幸运数

51nod1230：幸运数题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1230题目大意：如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，则称它为幸运数。例如：120是幸运数，因为120的数字... 查看详情

51nod1019逆序数（归并排序）

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1019题意：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序... 查看详情

51nod1107（树状数组逆序数）

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1107思路：其实就是升级版的逆序数，x坐标当作位置，y坐标当作数值val，只是可能有相等的数，稍作修改即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=... 查看详情

[51nod1230]幸运数（数位dp）

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1230dp(l,s,ss)表示长度为l的数各位和为s，各位平方和为ss的幸运数的个数。1#include<bits/stdc++.h>2#pragmacomment(linker,"/STACK:10240000,10240000")3usingnam 查看详情

51nod1002数塔取数问题

Input示例458 43 6 97 2 9 5Output示例28 查看详情

51nod1230幸运数

1230 幸运数题目来源： HackerRank基准时间限制：1 秒空间限制：131072 KB分值: 320 难度：7级算法题如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，... 查看详情

51nod1019逆序数

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。如2431中，21，43，41，31是逆序，逆序数是4。给出一个整... 查看详情

51nod1119组合数，逆元

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=11191119机器人走方格 V2基准时间限制：1秒空间限制：131072KB分值:10难度：2级算法题收藏关注M*N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？... 查看详情