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
题目连接：http://118.24.30.237/problem.php?id=3142
暴力想 从 只有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。
代码语言：javascript复制#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("%lldn",res[j]);
}
}方法二： 需要一定的思维过程 直接读代码就好咯 下图为确定区间的长度
#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("%lldn",res[i]);
}
return 0;
}
