「美团 CodeM 资格赛」数码 详解

举报
Fivecc 发表于 2022/08/29 14:01:00 2022/08/29
【摘要】 给定两个整数 l 和 r,对于任意 x,满足l≤x≤r ,把 x 的所有约数全部写下来。对于每个写下来的数,只保留最高位的那个数码。求[1,9]中每个数码出现的次数。

❓问题描述

3142: #6083. 「美团 CodeM 资格赛」数码

Time Limit: 1 Sec  Memory Limit: 256 MB

Description

给定两个整数 l 和 r,对于任意 x,满足l≤x≤r ,把 x 的所有约数全部写下来。对于每个写下来的数,只保留最高位的那个数码。求[1,9]中每个数码出现的次数。

输入格式

输入一行两个整数 l 和 r。

输出格式

一共 9 行。

第 i 行,输出数码 i出现的次数。

样例

样例输入

1 4

样例输出

4 2 1 1 0 0 0 0 0

数据范围与提示

1≤l≤r≤10^9

💡思路1

暴力想 从 只有1位数开始 然后2位 3 位 。。。。枚举到边界限对于最高位数位1的来说有 1 10 11 12 … 19 100 101 102 … 199 …. 假设我们求得区间是 1-k 。这样的话答案就是 k/1 + k/10 + k/11 + … k/199。 确实减少了计算量,倒是但枚举到 10000000 的时候就不合适了,再按上述方法枚举次数就太多了。

这个时候分母变得很大,可以利用这个特性来进行分块,例如 k/10000000 与 k/10009999 结果可能都一样(向下取整)。 我们可以将答案都相同的分为一块,这样枚举因子的时候就可以滑动了,从10000000直接滑倒10009999。

​代码

#include<stdio.h>
#include<string.h>
#define  ll long long
#define min(a,b) a>b?b:a 
ll res[11];
    void work(ll r,int f){
           
            for(ll u=1;u<=9;u++)//找 含 1~9的 
            {
                for(ll v=1;u*v<=r;v*=10)//从第只有一位数开始找 一直到超出r 
                {
                    ll p,Stat=u*v,End=min(u*v+v-1,r);//Stat End当前位数开始与结束 p当前步长 
                    for(ll i=Stat;i<=End;i+=p)
                    {
                        ll yb=r/i,mod=r%i;
                        p=1; 
                        p+=min(mod/yb,End-i);//防止超界 
                        res[u]+=f*(yb*p);
                    }
                }
            }
            
        }
int main(){ 
        ll l,r;
        while(scanf("%lld%lld",&l,&r)==2)
        {     memset(res,0,sizeof(res));
		      work(r,1);
              work(l-1,-1);
            for(int j=1;j<=9;j++)printf("%lld\n",res[j]);
        }
}

💡思路2

需要一定的思维过程 直接读代码就好咯   下图为确定区间的长度示意图

​代码

#include<stdio.h>
#include<string.h>
#define ll long long 

ll res[11];
ll get_sum(ll zb,ll yb,ll x){
ll ans = 0;
    if(yb>x)yb=x;//当前右边界大于限定边界 更新掉 
	  int k=x/yb; //  获取在限定边界中含有右边界值有多少个 
	   int mod=x%yb;// mod 
		while(1){ 
	  int d=(yb-mod)/(k+1);// 获得此段应该每一个小节应该减少的长度d(整数)此段宽度  
	 // yb-d=x/(k+1) --> d=yb-x/(k+1)-->d=[yb(k+1)-x]/(k+1) 因为 x=yb*k+mod 所以 d=(yb-mod)/(k+1)
	 // 找到范围内倍数个数同为k的左边界 
		   if(d*(k+1)<(yb-mod))	d++;
		   if(yb-d<zb)break;//结束条件 当前段的左边界 超出该步骤的左边界 
		   ans+=k*d;//k*d 代表 此范围 有k个倍数的约数 有连续的d 个 
		    ll yyb=yb;
		    yb=yb-d;//更新当前段的左边界  
			mod=(k*d+mod)%yb;//更新当前段的mod值 c此时 yb 为 yb' 
	// mod=x/yb' --> x=yb*k+mod=(yb'+d)*k+mod=yb'*k+d*k+mod  --> mod= (d*k+mod)%yb'
		    int k12=k;
		   if(d==1)k=x/yb;//到了边界 
		  else k++;//更新 k   
		}
		ans+=(yb-zb+1)*k;
	return ans;
}
void work(int x,int v){
	ll i;
	for(i=1;i<10;i++){
    	ll w = 1;
		while(i*w<=x){
			ll end = i*w+w-1;
			res[i] += v*get_sum(i*w,end,x);
			w*=10;
		}
	}	
}
int main(){
     int n,m;
	while(~scanf("%d%d",&n,&m)){
		memset(res,0,sizeof(res));
		work(m,1);  
		work(n-1,-1);
		for(int i=1;i<10;i++)
		printf("%lld\n",res[i]);
	}
	return 0;
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。