每日一练Day 1

NC13221 数码

题解：
题目要求找到中的所有的数的约数出现的次数，如果存在多位数则只取最高位的贡献。
首先需要知道的一个数学知识是：中出现i的约数有个，那么我们就只需要考虑约数的数目。即：。
但是现在要求我们对于多位数，只需要考虑他的最高位的贡献，那我们就维护一个最高位的数字，每次查询它的最大区间长度即可。
AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define me(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define ull unsigned long long
#define ios std :: ios :: sync_with_stdio(false)
#define rep(i,a,b) for(int i = a;i <= b;i ++)
#define esp 1e-16
#pragma warning(disable:4996)

using namespace std;

ll read() 
{
    ll x = 0, f = 1; char c = getchar();
    while (c < '0' || c>'9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

ll l, r;
ll mi[20] = {};

ll solve(ll n, ll x)
{
    ll ans = 0ll;
    for (ll l = 1ll, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ll rep = 0ll;
//        cout << l << ' ' << r << endl;
        for (int i = 0; i <= 9; i++) rep += max(0ll, min(r, ((x + 1) * mi[i] - 1)) - max(l, x * mi[i]) + 1);
        ans += rep * (n / l);
    }
    return ans;
}

int main()
{
    ios;
    l = read(); r = read();
//    cout << r << ' ' << l << endl;
    mi[0] = 1;
    for (int i = 1; i < 10; i++) mi[i] = mi[i - 1] * 10;
    for (int i = 1; i <= 9; i++) cout << solve(r, i) - solve(l - 1, i) << endl;
    return 0;
}