SPOJ LCMSUM - LCM Sum

题意是求：

　　　　$\sum_{i = 1}^{n}lcm(i, n)$

　　　　$= \sum_{i = 1}^{n}\frac{ni}{gcd(i, n)}$

　　　　$= n\sum_{i = 1}^{n}\frac{i}{gcd(i, n)}$

　　　　$= n\sum_{d|n}\sum_{i = 1}^{n}d*[gcd(i, n)==d]$

　　　　$= n\sum_{d|n}\sum_{i = 1}^{\frac{n}{d}}i*[gcd(i, \frac{n}{d})==1]$

　　　　$= n\sum_{d|n}\sum_{i = 1}^{d}i*[gcd(i, d)==1]$

设$h(d) = \sum_{i = 1}^{d}i*[gcd(i, d)==1]$，其实是求在$1,2,3...d$的范围内与$d$互质的数的总和，当$d>1$时，它就等于$\frac{\phi (d) * d}{2}$

证明：

　　　　因为$gcd(i, d) == 1$，那么也有$gcd(d - i, d) == 1$，所以假如$i$与$d$互质，那么$d - i$也与$d$互质，它们的和是$d$，也就是说在$1, 2, 3, ..., d$中，这样的数对一共有$\frac{\phi (d)}{2}$个，每一对的和是$d$，所以$h(d) = \frac{\phi (d) * d}{2}$

$h(1)$当然是等于$1$的。

这样我们线性筛出欧拉函数$\phi (i)$，然后再暴力算$h(i)$，最后询问的时候输出$h(n) * n$.

时间复杂度是$O(MaxNlogMaxN + T)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e6 + ;

const int Maxn = 1e6;

int testCase, pCnt = , pri[N];

ll h[N], phi[N];

bool np[N];

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

void sieve() {

    phi[] = 1LL;

    for(int i = ; i <= Maxn; i++) {

        if(!np[i]) pri[++pCnt] = i, phi[i] = i - ;

        for(int j = ; j <= pCnt && pri[j] * i <= Maxn; j++) {

            np[i * pri[j]] = ;

            if(i % pri[j] == ) {

                phi[i * pri[j]] = phi[i] * pri[j];

                break;

            }

            phi[i * pri[j]] = phi[i] * (pri[j] - );

        }

    }

    for(int i = ; i <= Maxn; i++) {

        ll now = phi[i] * i / ;

        if(i == ) now = 1LL;

        for(int j = i; j <= Maxn; j += i)

            h[j] += now;

    }

}

int main() {

    sieve();

    for(read(testCase); testCase--; ) {

        int n; read(n);

        printf("%lld\n", 1LL * n * h[n]);

    }

    return ;

}

———————————————————————————————————————————————————

upd：

去看了一下题解，发现其实可以线性筛$h(i) $，感觉很神仙。

下文中的$h(d) = \sum_{t | d} \phi (t) * t$

因为$\phi (t)$和$t = N(t)$都是积性函数，所以$\phi (t) * t$也是积性函数，那么$h(i)$就相当于$\phi(i) * i$与$1$的卷积，所以$h(i)$也是积性函数，可以线性筛。

　　$h(p) = (p - 1) * p + 1 = p^2 - p + 1$

　　$h(p^k) = h(p^k) = \sum_{i = 0}^{k}p^i * \phi (p^i) = p^2\sum_{i = 0}^{k - 1}p^i * \phi (p^i) - p + 1$

因为$\phi (p) = p - 1$，而$\phi (p^k) = \phi (p^{k - 1}) * p = (p - 1) * p^{k - 1}$，所以相当于多乘了一个$p$，把它减掉，然后加上第一项$1$。

最后算答案的时候注意到这时候$\phi (1)$是取$2$的，所以最后输出$\frac{(h(n) + 1)}{2}$。

时间复杂度$O(MaxN + T)$。

不想实现。

巴特西

SPOJ LCMSUM - LCM Sum

最新文章

热门文章