牛客網題庫——1數位

問題描述：

       給定兩個整數

 和 

，對于所有滿足1 ≤

 ≤

 ≤

≤ 10^9 的

，把 

 的所有約數全部寫下來。對于每個寫下來的數，隻保留最高位的那個數位。求1～9每個數位出現的次數。

輸入描述：

一行，兩個整數  和  (1 ≤  ≤  ≤ 10^9)。
           

輸出描述:

輸出9行。

第 i 行，輸出數位 i 出現的次數。
           

示例1

輸入

1 4

輸出

4
2
1
1
0
0
0
0
0
           

問題轉化：

 , 即

 與

之間的所有整數的所有約數的最高數位數位頻數 等于 1到

之間的所有整數的此項問題解 與 1到

 -1之間的所有整數的此項問題解  的差 

求解思路：    對于問題

, 考慮采用枚舉約數的方式求解，周遊其中所有的整數，對于每一個整數，考量其都可以作為誰的約數，然後計數其被約數的個數，将此個數累加在該數最高位數位頻數上

具體求解方法：

1.  對于整數M，其被約數有M， 2M， 3M， ... (不超過n) ，那麼被約數個數可以這樣求得

2.  在枚舉約數時，鑒于問題求的是最高數位頻數，拟将所有約數以數量級劃分階段進行處理，不妨設其最高數位p和位數q (依題意得q不大于10)，這樣每個階段的第一個數可以表示為

，最後一個數可以表示為

那麼對于數位p，其頻數就可以這樣計算了

3.  枚舉約數時，有一個規律值得我們注意，緊鄰的幾個數往往具有相同個數的被約數，充分利用這個規律将會大大加快我們的枚舉速度。對于數M，其後面跟着幾個與其擁有相同個數被約數的整數呢，這個我們要用到數M除n之後的餘數rema，看看餘數裡還夠整數M增加幾個1，設d = 

，則整數M每增一，餘數就減去一個d。照如此算，整數M之後還有

個整數與其擁有相同個數的被約數

#include <bits/stdc++.h>
using namespace std;
typedef long long ll_int;
ll_int l, r;
   
vector<ll_int> solve(ll_int r) {   //設r = 100
    vector<ll_int> ans(10, 0);
    for(ll_int u = 1; u <= 9; ++u) {  //u為最高位數位  設此時u = 3
        for(ll_int v = 1; u * v <= r; v *= 10) {  // u * 10^   ，設此時v = 10
            ll_int s = u * v, e = min(u * v + v - 1, r);    // s = 30 e =min( 39, 100)
            ll_int slip;
            for(ll_int i = s; i <= e; i += slip) {  
                //采用快速求解 此時30 31 32 33的mult是一緻的，故可以不必再去周遊31 32 33，
                ll_int mult = r / i, rema = r % i;   //mult = 3， rema = 10
                slip = 1; slip += min(rema / mult, e - i);   
                //一般情況下采用的都是rema / mult ， 目前周遊值每增一，總的就增一個mult，
                //故需要計算餘數中還可容納幾個相同商的約數
                ans[u] += mult * slip;
            }
        }
    }
    return ans;
}
   
int main(void) {
    while(~scanf("%lld%lld", &l, &r)) {
        vector<ll_int> ans1 = solve(l - 1);
        vector<ll_int> ans2 = solve(r);
        for(int i = 1; i <= 9; ++i)
            printf("%lld\n", ans2[i] - ans1[i]);
    }
}
           

連結：https://ac.nowcoder.com/acm/problem/13221

來源：牛客網