题解 | #C计数问题的O(n)解法#

C——计数问题O(n)解法

通过枚举不难发现，本题的答案就是 ${\sum }_{i=1}^{n-1}d(i)d(i-1)\backslash sum\_\{i=1\}^\{n\; -\; 1\}d(i)d(i-1)$。

约数和函数 $d(n)d(n)$ 是常见的积性函数，积性函数可以在 $O(n)O(n)$ 时间复杂度(结合欧拉筛)筛出 $d(1)d(1)$ 到 $d(n)d(n)$的值。本题的时间复杂度可以加强到 $1e71e7$。

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int primes[N], cnt;
bool st[N];
int d[N], e[N]; //约数和 最小质因子的个数
int n;

void init(int n)
{
    d[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt ++ ] = i, d[i] = 2, e[i] = 1;
        for (int j = 0; i * primes[j] <= n; j++)
        {
            int p = primes[j];
            st[i * p] = true;
            if (i % p == 0) //如果p为i的最小质因子
            {
                //i * p的最小质因子个数 + 1, 需要除去之前的贡献, 乘以新的贡献
                d[i * p] = d[i] / (e[i] + 1) * (e[i] + 2);
                e[i * p] = e[i] + 1;
                break;
            }
            //p此时为i * p的最小质因子, 且个数为1
            d[i * p] = d[i] * d[p]; //i和p互质, 结合积性函数的性质d(i * p) = d(i) * d(p)
            e[i * p] = 1;
        }
    }
}

void solve()
{
    int n;
    cin >> n;
    init(n);
    LL res = 0;
    for (int i = 1; i < n; i++)
        res += 1ll * d[i] * d[n - i];
    cout << res << endl;

}

int main()
{
    int T = 1;
    // cin >> T;
    while (T -- ) solve();
    return 0;
}