美团codeM资格赛 数码

数码

时间限制：1秒

空间限制：32768K

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

输入描述:

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

输出描述:

输出9行。

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

输入例子:

1 4      

输出例子:

4
2
1
1
0
0
0
0
0      

解题思路：求[a,b]的问题，拆成求[1,b]-[1,a-1]的问题。在[1,x]中，有约数y的数有x/y个。假设x为常数，对函数f(y)=x/y，在y=1,2,3...n上的点用曲线近似，是反比例函数在第一象限的图像。特点：前半段很陡峭，差个1，函数值都差远了；后半段很平坦，n/2个数的函数值都为1。根据这两段的不同情况，采取不同的处理策略：对前半段（比如，1到10万），直接算有多少个数包含这个约数x，直接加到答案上。对后半段（10万以上），我们计算有多少个约数，只有1个、2个....个数的约数中包含它，这些数的取值范围是多少。然后统计出这些约数中，有多少是以1、2、3...9开头的数，乘上相应的约数个数，加到答案中。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;

LL a[10],b[10],cnt[10];
int x[100009];

void f(int l,int r)
{
    memset(cnt,0,sizeof cnt);
    char ch[15];
    while(l<=r)
    {
        sprintf(ch,"%d",r);
        int k=ch[0]-'0';
        for(int i=1; ch[i]; i++) k=k*10;
        if(k<l) k=l;
        cnt[ch[0]-'0']+=r-k+1;
        r=k-1;
    }
}

void get(int k,LL a[])
{
    for(int i=1; i<=100000; i++)
        a[x[i]]+=k/i;
    if(k<=100000)return;
    int p=k;
    for(int i=1;; i++)
    {
        int kk=k/(i+1);
        kk++;
        if(kk<=100000) kk=100001;
        f(kk,p);
        for(int j=1; j<=9; j++) a[j]+=cnt[j]*i;
        p=k/(i+1);
        if(p<=100000) break;
    }
}

int main()
{
    for(int i=1; i<=9; i++)
        for(int j=1; j<=10000; j*=10)
            for(int k=0; k<j; k++) x[i*j+k]=i;
    x[100000]=1;
    int l,r;
    while(~scanf("%d%d",&l,&r))
    {
        get(r,b);
        get(l-1,a);
        for(int i=1; i<=9; i++) printf("%lld\n",b[i]-a[i]);
    }
    return 0;
}