【51Nod 1363】最小公倍数之和

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1363

\[\begin{aligned}
&\sum_{i=1}^n\frac{in}{(i,j)}\\
=&n\sum_{d|n}\sum_{i=1}^{\frac nd}\left[\left(i,\frac nd\right)=1\right]i\\
=&n\left(1+\sum_{d|n,d\neq n}\sum_{i=1}^{\left\lfloor\frac {n}{2d}\right\rfloor}\left[\left(i,\frac nd\right)=1\right]\right)\\
=&n+\frac n2\sum_{d|n,d\neq 1}d\varphi(d)
\end{aligned}
\]

重点是统计\(\sum\limits_{d|n,d\neq 1}d\varphi(d)\)

\[\begin{aligned}
&\sum_{d|n,d\neq 1}d\varphi(d)\\
=&\prod\sum_{j=0}^{c_i}p_i^j\times\varphi\left(p_i^j\right)-1\\
=&\prod\left(1+\sum_{j=1}^{c_i}p_i^{2j-1}\left(p_i-1\right)\right)-1\\
=&\prod\left(1+\frac{p_i^{2c_i+1}-p_i}{p_i+1}\right)-1
\end{aligned}
\]

质因子分解统计就可以了，时间复杂度\(O\left(T\sqrt n\right)\)。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 100000;

const int p = 1000000007;

bool notp[N + 3];

int T, n, prime[N + 3], num = 0, ni[N + 3];

void Euler_shai() {

	for (int i = 2; i <= N; ++i) {

		if (!notp[i]) prime[++num] = i;

		for (int j = 1; j <= num && prime[j] * i <= N; ++j) {

			notp[prime[j] * i] = true;

			if (i % prime[j] == 0) break;

		}

	}

	ni[1] = 1;

	for (int i = 2; i <= N; ++i)

		ni[i] = 1ll * (p - p / i) * ni[p % i] % p;

}

int ipow(int a, int b) {

	int r = 1, w = a;

	while (b) {

		if (b & 1) r = 1ll * r * w % p;

		w = 1ll * w * w % p;

		b >>= 1;

	}

	return r;

}

int cal(int x) {

	int ret = 1, ci;

	for (int i = 1, pi = 2; i <= num && pi * pi <= x; pi = prime[++i]) {

		if (x % pi == 0) {

			ci = 1; x /= pi;

			while (x % pi == 0) x /= pi, ++ci;

			ret = 1ll * ret * (1ll * (ipow(pi, 2 * ci + 1) - pi + p) % p * ni[pi + 1] % p + 1) % p;

		}

	}

	if (x > 1) {

		ret = 1ll * ret * ((1ll * x * x % p * x % p - x + p) % p * ipow(x + 1, p - 2) % p + 1) % p;

	}

	return ret;

}

int main() {

	Euler_shai();

	scanf("%d", &T);

	while (T--) {

		scanf("%d", &n);

		printf("%lld\n", (1ll * n * ni[2] % p * (cal(n) - 1) % p + n) % p);

	}

	return 0;

}

巴特西

【51Nod 1363】最小公倍数之和

最新文章

热门文章