ABC162E (AT5310)

· · 题解

UPD on 8.14 更新时间复杂度分析

这里欧拉反演的优势就体现出来了 .

主要就是借助范德蒙德卷积恒等式 \varphi*1=\mathrm{Id}，也就是

\sum_{d\mid n}\varphi(d)=n

接下来对原式进行一些基本操作

\begin{aligned}\sum_{a_1=1}^k\sum_{a_2=1}^k\dots\sum_{a_n=1}^k\gcd(a_1,a_2,\dots,a_n)&=\sum_{a_1=1}^k\sum_{a_2=1}^k\dots\sum_{a_n=1}^k\sum_{d\mid\gcd(a_1,a_2,\dots,a_n)}\varphi(d)\\&=\sum_{d=1}^k\varphi(d)\left\lfloor\dfrac kd\right\rfloor^n\end{aligned}

然后就是老生常谈的东西了，先整除分块，然后肯定要线性筛欧拉函数 .

此时的时间复杂度是 O(k+\sqrt n\log k)，带一个快速幂的 \log .

然而指数一定我们就可以线性筛 f(x)=x^n，因为 f 是完全积性函数所以非常好实现 .

然而此时预处理的时间复杂度变成

T(n)=\sum_{\substack{p\le n\cr p\text{ is prime}}}\log p

根据素数定理 \pi(n)\sim\dfrac n{\ln n}，有预处理时间复杂度上界 T(n)=O\left(\pi(n)\log n+n\right)=O(n)

于是可以做到 O(k+\sqrt n)，非常的优秀啊 .

目前是最优解 rk4 .

至少在我发这篇题解的时候是这样，前面仨老哥都是带 \log 复杂度然后卡卡常 .

可能我代码自带大常数吧 QwQ .

代码：

#include <bits/stdc++.h>
template<typename T>
inline T chkmin(T& x, const T& y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, const T& y){if (x < y) x = y; return x;}
using namespace std;
const int N = 114514, P = 1e9+7;
bool notprime[N];
int n, k, phi[N], power[N];
vector<int> plist;
inline int qpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n & 1) ans = 1ll * ans * a % P;
        a = 1ll * a * a % P; n >>= 1;
    } return ans; 
}
inline void linear_sieve()
{
    notprime[1] = true; phi[1] = power[1] = 1;
    for (int i=2; i<=k; i++)
    {
        if (!notprime[i]){plist.emplace_back(i); power[i] = qpow(i, n); phi[i] = i-1;}
        for (auto x : plist)
        {
            int now = i*x;
            if (now > k) break;
            notprime[now] = true;
            if (!(i%x)){phi[now] = phi[i] * x; power[now] = 1ll * power[i] * power[x] % P; break;}
            power[now] = 1ll * power[i] * power[x] % P; phi[now] = phi[i] * phi[x];
        }
    }
    for (int i=1; i<=k; i++) phi[i] = (phi[i] + phi[i-1]) % P;
}
int main()
{
    scanf("%d%d", &n, &k); linear_sieve();
    int ans = 0;
    for (int l=1, r; l <= k; l = r+1)
    {
        r = k / (k / l);
        ans = (ans + 1ll * (phi[r] - phi[l-1]) % P * power[k / l] % P) % P; 
    } printf("%d\n", (ans + P) % P);
    return 0;
}