首页 > 其他分享 >CF55D Beautiful numbers

CF55D Beautiful numbers

时间:2024-05-09 10:36:12浏览次数:18  
标签:Beautiful 2520 int pos 公倍数 numbers CF55D 整除 dp

题目链接:https://www.luogu.com.cn/problem/CF55D

数位dp
解法:所有非零位都能整除这个数,那么就是说这些非零位的公倍数能够整除这个数。

那么按照通常情况我们定义dp数组的时候应该定义成dp[pos][num][gbs],表示当前枚举到了第几位、上次枚举到的数、之前所有数位的最小公倍数。那么题目范围一共有9e18,第一维只用开20即可,那么第二维显然不能开9e18.第二维我们处理的方法是:既然我们要讨论的是这个num能否被其之前所有非零位的最小公倍数整除,那么所有非零数位的可能只有1-9 共9个数,1-9的最小公倍数是2520.那么我们只需要考虑num%2520的结果能否被最小公倍数整除就行了。因为2520一定能被最小公倍数整除,取模就是把一定能被整除的那些数去掉,剩下的数是不一定能被整除的。

那么第二维只用开2521的大小即可。接下来我们考虑所有公倍数的情况。刚刚我们已经知道1-9 9个数的最小公倍数是2520,那么假如第三维开2521的大小,数组将会达到越近1e8的量级,依然会爆。那么我们考虑将2520的因子离散化。2520的因子有48个,打个表就很容易得出,所以第三维只用开50就行了。这样开数组就不会爆炸了。

那么接下来就是记忆化搜索写法的数位dp的基本操作了,数位dp处理答案使用到的是差分的思想,这个是数位dp的基操。具体见注释。


inline int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}//gcd(a,b)=gcd(a,b-a)(b>a);
inline int lcm(int a, int b){return a / gcd(a, b) * b;}//lcm(n,m)=n*m/gcd(n,m)
#define int long long
int dp[30][3000][50];
int lsh[3000];
int a[60];
int dfs(int pos,int lim,int mo,int gbs)
//当前处理第几位,是否有大小限制,当前的值对2520取模的结果,当前的公倍数
{
    if(!pos)
    {
        if(mo%gbs==0) return 1;//如果这个数能够被非零位的公倍数整除那么就统计进答案
        else return 0;//否则就不
    }
    //记忆化搜索
    if(!lim&&~dp[pos][mo][lsh[gbs]]) return dp[pos][mo][lsh[gbs]];
    int up=lim?a[pos]:9;//上界
    int res=0;
    for(int i=0;i<=up;i++)
    {
        res+=dfs(pos-1,lim&&i==up,(mo*10+i)%2520,i!=0?lcm(gbs,i):gbs);
        //处理下一位。mo*10+i就是该数加上下一位之后的新的数,加上了非零位的数要更新其公倍数
        //在这个数的最后一位加上之前 %2520对答案都没有影响
    }
    if(!lim) dp[pos][mo][lsh[gbs]]=res;
    return res;
}
int calc(int x)
{
    memset(a,0,sizeof(a));
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,1,0,1);
    //注意,最后gbs这里初始要传1进去,不然更新公倍数的时候会出问题(除0)
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int idx=0;
    for(int i=1;i<=2520;i++)
    {
        if(2520%i==0)
        {
            lsh[i]=++idx;//把2520的每个因子离散化下来
        }
    }
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));//记忆化搜索需要用到,这一行不能写while(t--)里面
    while(t--)
    {
        int l,r;
        cin>>l>>r;
        cout<<calc(r)-calc(l-1)<<'\n';
    }
    return 0;
}

标签:Beautiful,2520,int,pos,公倍数,numbers,CF55D,整除,dp
From: https://www.cnblogs.com/captainfly/p/18181556

相关文章

  • LeetCode 2597. The Number of Beautiful Subsets
    原题链接在这里:https://leetcode.com/problems/the-number-of-beautiful-subsets/description/题目:Youaregivenanarray nums ofpositiveintegersanda positive integer k.Asubsetof nums is beautiful ifitdoesnotcontaintwointegerswithanabsolut......
  • CF1842H Tenzing and Random Real Numbers 题解
    题目链接点击打开链接题目解法实数的概率好反直觉!对\(1\)做限制不是很好做,考虑变成正负性的限制(即对\(0\)做限制)令\(y_i=x_i-0.5\),那么限制就变成了\(y_i+y_j\le0,\;y_i+y_j\ge0\)这里要给出一些实数概率的结论:实数下,\(x=y\)的概率为\(0\),因为\(\frac{1}{\inft......
  • [题解]CF55D Beautiful Numbers
    CF55DBeautifulNumbers打出暴搜后有些茫然,不知道该怎么优化才好,看了题解才豁然开朗。简单说下暴搜的思路:参数有\(pos,limit,lcm,num\)。其中\(lcm\)表示到\(pos+1\)位,所有非\(0\)位的\(lcm\)是多少;\(num\)表示填到\(pos+1\)位的整个数是多少。然后在\(pos=0\)时判断\(lcm\)是......
  • [题解]SP10606 Balanced Numbers
    SP10606BalancedNumbers关于优化方式的说明详见数位dp例题及详解-下。SPOJ注册不上所以暂时无法提交w,但是3份代码与正解对拍没有问题。使用\(vis[0\sim9]\)表示\(0\sim9\)的访问情况,\(sta[0\sim9]\)表示\(0\sim9\)填写个数的奇偶性(奇数为\(1\),偶数为\(0\))。暴搜先打出来,......
  • CF244B Undoubtedly Lucky Numbers 题解
    题目简述给定一个$n$,问有多少个小于等于$n$的数只由两个不同的数字$x$和$y$组成。题目分析直接枚举肯定不行,我们考虑枚举$x$和$y$,再利用深搜,生成所有不大于$n$且只由$x$和$y$组成的数字,利用map去重,统计答案即可。代码#include<iostream>#include<map>usi......
  • 52 Things: Number 22: How do you represent a number and multiply numbers in Mont
    52Things:Number22:HowdoyourepresentanumberandmultiplynumbersinMontgomeryarithmetic?52件事:数字22:在蒙哥马利算术中,你如何表示一个数字并将其相乘? Thisisthelatestinaseriesofblogpoststoaddressthelistof '52ThingsEveryPhDStudentSh......
  • [题解][2022江西省程序设计大赛] A Game of Taking Numbers
    题目描述rqdmap和他的小女友正在玩一个游戏。有n个正整数。这两个人轮流取数字。为了显示他的绅士风度,rqdmap要求他的小女友先取数字。每当rqdmap的小女友可以选择剩下的数字中的任意一个来拿走(记为x),rqdmap需要从剩下的数字中选择一个数字(记为y),并且满足以下两个条件中的至少一个......
  • 手把手教你做阅读理解题-初中中考阅读理解解题技巧015-Explore Beautiful Lake Charle
    PDF格式公众号回复关键字:ZKYD015阅读理解技巧,在帮助读者有效获取和理解文本信息方面发挥着重要作用,熟练掌握如下6个技巧,可快速突破阅读理解1预览文章结构在开始深入阅读之前,快速浏览文章的标题、段落开头和结尾,可以迅速把握文章的主题、大致内容和结构标题通常能概括文章......
  • Python爬虫+认识html网页文本文件,使用beautifulSoup获取信息
    认识HTMLHTML参考手册:https://www.w3cschool.cn/htmltags/tag-p.htmlHTML线上教程:https://www.runoob.com/html/html-examples.html 菜鸟教程html在线编程器:https://www.runoob.com/try/try.php?filename=tryhtml_comment 提示:将下面代码复制到 菜鸟教程html在线编程......
  • E. Vlad and a Pair of Numbers
    题解首先,我们知道异或运算是无进位相加,那么a^b=x我们不妨先让a=x,b=0;而a,b其余二进制位上要么同为0,要么同为1。接下来,根据题意a+b=2x,我们可知我们同时为a,b加上x/2。此时再判断a^b是否等于x即可。code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intma......