数码

AC代码如下

//cpp
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
//枚举d的长度为q，q取值1~10，将10^(q-1)值保存到pow中
vector m_pow = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };
ll getSum(ll n,ll m) {
    if (n == 0 || m == 0) {
        return 0;
    }
    m = min(n, m);
    ll res = 0;
    ll t = 0;
    ll cnt;
    for (t = 1; t <= m && (t*t) <= n; t++) {
        res += n / t;
    }
    for (ll k = n / t; k >= n / m; k--) {
        cnt = min(m, n / k) - n / (k + 1);
        res += k*cnt;
    }
    return res;
}
//计算[1,num]内约数情况
void getFactors(ll num, vector& res) {
    for (int p = 1; p <= 9; p++) {   //p为枚举d的数码 1~9
        for (int q = 1; q <= 10; q++) {  //j表示枚举d的长度q  1~10  
            if ((p * m_pow[q - 1] - 1) > num) {
                break;
            }
            else {
                res[p] += (getSum(num, min(num,(p + 1) * m_pow[q - 1] - 1)) - getSum(num, p * m_pow[q - 1] - 1));
            }
        }
    }
}
int main(){
    ll left, right;
    while (cin >> left >> right) {
        vector res1(10);  //用于记录结果
        vector res2(10);  //用于记录结果
        getFactors(left-1,res1);
        getFactors(right, res2);
        for (int i = 1; i <= 9; i++) {
            cout << res2[i] - res1[i] << endl;
        }
    }
    system("pause");
    return 0;
}

考虑[left,right] = [1,right] - [1,left-1]，将问题转化为[1,right]和[1,left-1]两个子区间问题。下面只要求解[1,n]区间问题即可。 对于一个数d，它是d，2d，3d， ... 的约数，也就是区间[1, n]内约数d出现的次数为n/d（向下取整）。 考虑枚举约数d的数码p（即最高位的值）和数字位数q，那么有d属于[p10^(q-1),(p+1)10^(q-1))。例如，最高位为1的约数d出现在[1,2)，[10,20)，[100,200) 等区间；最高位为4的约数d出现在[4,5)，[40,50)，[400,500) 等区间。 > 这样划分区间的好处是区间中值的最高位都一样，方便统计。不用再去求解约数的最高位。 > 由于d最大是10^9，因此，通过上式计算得，q最大取值为10。

参照上图，计算约数为p的个数为

//枚举d的长度为q，q取值1~10，将10^(q-1)值保存到pow中
vector m_pow = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };
for (int p = 1; p <= 9; p++) {   //p为枚举d的数码 1~9
    for (int q = 1; q <= 10; q++) {  //j表示枚举d的长度q  1~10  
        res[p] += (getSum(num, (p + 1) * m_pow[q - 1] - 1) - getSum(num, p * m_pow[q - 1] - 1));
    }
}

对上述算法再进行优化，限制区间小于等于num。

for (int p = 1; p <= 9; p++) {   //p为枚举d的数码 1~9
    for (int q = 1; q <= 10; q++) {  //j表示枚举d的长度q  1~10  
        if ((p * m_pow[q - 1] - 1) > num) {
            break;
        }
        else {
            res[p] += (getSum(num, min(num,(p + 1) * m_pow[q - 1] - 1)) - getSum(num, p * m_pow[q - 1] - 1));
        }    
    }
}

下面分析如何计算Sum(n,m)。如果直接计算，则复杂度为O(n)。牛客网系统仍然会判断超时。应该对算法进行优化处理，这也是本题的难点。

对应的代码实现为

for (ll k = n / t; k >= n / m; k--) {
    cnt = min(m, n / k) - n / (k + 1);
    res += k*cnt;
}

function sol(a, b) {
    var ret = [0,0,0,0,0,0,0,0,0];
    for(let i=a; i<=b; i++) {
        iter(i, ret);
    }
    return ret;
}

function iter(x, ret) {
    var num1;
    var num2;
    for(let i=1; i*i<=x; i++) {

        if(x % i == 0) {
            num1 = i;
            num2 = x/i;
            while(num1/10 >= 1){
                num1 = Math.floor(num1/10);
            }
            if(num2 != num1){
                while(num2/10 >= 1){
                    num2 = Math.floor(num2/10);
                }
                ret[num2-1] += 1;   
            }
            ret[num1-1] += 1;
        }
    }
}

var data = readline().split(' ');
var a = parseInt(data[0]);
var b = parseInt(data[1]);
var result = sol(a,b);
for(let i=0; i<9; i++) {
    print(result[i]);
}

相对于暴力遍历，这里面我只加了

for(let i=1; i*i<=x; i++)

这一个优化，应该时间复杂度可以到 o(n√n)的，但是结果出错，32-8300的例子，返回的数字不对，有没大神帮我看下我哪里出了bug？只是缩小了一下遍历范围呀。

	importjava.util.Scanner;



	publicclassMain {



	    publicvoidgetx(intl,intr){



	        if((r>=l)&&(r<=10e9)){



	            int[] temp = getArray(l,r);



	            int[] amount = newint[9];



	            for(intm=1;m<=9;m++){



	                for(inti=0;i<temp.length;i++){



	                    if(temp[i]%m==0){



	                        amount[m-1]++;



	                    }



	                }



	            }



	            for(intnum:amount){



	            System.out.println(num);



	            }          



	        }else{



	            System.out.println("输入数值的范围有误，请重试（1 ≤ l ≤ r ≤ 10^9）");



	        }



	    }



	    privateint[] getArray(inta,intb){



	        int[] array=newint[Math.abs(a-b)+1];



	        if(a<b){



	            for(inti=0;i<=b-a;i++){



	                array[i]=a+i;



	            }



	            returnarray;



	            }else{



	            for(inti=0;i<=a-b;i++){



	                array[i]=b+i;



	                //System.out.println("array"+i+array[i]);



	            }



	            returnarray;



	        }



	         



	         



	    }



	     



	    publicstaticvoidmain(String args[]){



	        Main codem=newMain();



	        Scanner in = newScanner(System.in);



	        while(in.hasNextInt()){



	            inta=in.nextInt();



	            intb=in.nextInt();



	            codem.getx(a, b);



	        }



	    }



	}