中国计量大学现代科技学院第四届“中竞杯”程序设计校赛 E.数论只会 for 循环

题目描述

https://ac.nowcoder.com/acm/contest/9680/E

Solution

注意到每次 $n$ 至少变小一半，所以 $k$ 只有小于 $\log n$ 才有用

那么我们现在不考虑 $k$，最后复杂度乘上个 $k$ 即可

我们考虑数论分块，对于每个区间 $[l,r]$ 我们直接暴力找不同的 $\lceil log_2 i \rceil$ 即可

时间复杂度 $O(\sqrt n\log^2n)$

#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 1000000007;

int n, m;

struct Div_hash {
    int n, sn; bool f;

    void init(int _n) { n = _n; sn = sqrt(n); }

    int get(int x) { return x <= sn ? x : sn * 2 - n / x + 1; } 
} _;

ll f[maxn][30];
ll dfs(int n, int d) {
    if (d == m) return 1;
    if (~f[_.get(n)][d]) return f[_.get(n)][d];
    ll ans = 0, k = 1;
    for (ll l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l); ll sum = 0, la = l;
        while ((1 << k) < l) ++k;
        while ((1 << k) <= r) {
            sum += k * ((1 << k) - la + 1);
            la = (1 << k) + 1; ++k;
        } sum = (sum + k * (r - la + 1)) % p; 
        ans = (ans + sum * dfs(n / l, d + 1)) % p;
    } return f[_.get(n)][d] = ans;
} 


int main() { fill(f[0], f[0] + maxn * 30, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; _.init(n); 
    cout << dfs(n, 0) << "\n";
    return 0;
}