【每日一题】4月6日数码

数码

https://ac.nowcoder.com/acm/problem/13221

题目:数码
来源:美团2017年CodeM大赛-资格赛

时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format:%lld

题目描述

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

输入描述:

一行,两个整数 l 和 r (1 ≤ l ≤ r ≤ 10^9^)。

输出描述:

输出9行。

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

示例1
输入

1 4

输出

4
2
1
1
0
0
0
0
0

题解:
先介绍一个函数:
solve(a,b)就是从1a中数码b的倍数出现的次数
solve(a,b)=a/b
那么求[l,r]的话,就用solve(r,b)-solve(l-1,b),大致可以理解成前缀和那种
num就是0
9,计算每个num对应的区间
最高位是1的话:1,10 ~ 19,100 ~ 199, 1000 ~ 1999....
最高位是2的话:2,20 ~ 29,200 ~ 299, 2000 ~ 2999....
....
因为我们只记录约数的最高位,像1999,约数就是1和1999,我们只记录最高位,那么就是有两个1
那么我们枚举以num开头的数,计算它的倍数在[l,r]中出现的次数。
按照几位数和最高位是几进行枚举,有多少这样的数直接统计就ok
solve(r,num)-solve(l-1,num)
枚举num的值
让最高位等于x时num枚举相对应的区间(从x10^y-1^~(x+1)10^y-1^-1)y=1.2.3....
有部分数会被算重复,因为有完全平方数存在,
再运用整除分块技巧,让复杂度降到O(根号n)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll minn(ll a,ll b)
{
    if(a>=b)
    {    
        return b;

    }
    else 
    {
    //    cout<<a;
     return a;

    }
}
ll solve(ll a, ll b) {
  ll res = 0;
   ll beg;
   ll end;
  for (ll i = 1; i <= a / b; i *= 10) {
    beg = b * i;//区间开头

     end = minn(a, beg + i - 1);//区间结尾
     int k;
    for (int j = beg; j <= end; j = k + 1) {
      k = min(a / (a / j), end);
      //cout<<a/(a/i)<<" "<<end<<endl;
      res += (k - j + 1) * (a / j);
    }
  }
  return res;
}
ll l,r;
int main(){
   cin>>l>>r;
    for(ll i=1;i<=9;i++){
        cout<<solve(r,i)-solve(l-1,i)<<endl;
    }
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
球球别再泡了:坏,我单9要了14
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务