P1891 疯狂LCM

\(\color{#0066ff}{ 题目描述 }\)

众所周知，czmppppp是数学大神犇。一天，他给众蒟蒻们出了一道数论题，蒟蒻们都惊呆了。。。

给定正整数N，求LCM(1,N)+LCM(2,N)+...+LCM(N,N)。

\(\color{#0066ff}{输入格式}\)

第一行一个数T，表示有T组数据。

对于每组数据，一行，一个正整数N。

\(\color{#0066ff}{输出格式}\)

T行，每行为对应答案。

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

对于30%的数据，1≤T≤5，1≤N≤100000

对于100%的数据，1≤T≤300000，1≤N≤1000000

\(\color{#0066ff}{ 题解 }\)

题目要求

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

转为gcd形式

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

枚举gcd

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

把d弄前面去

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

额，后面的的东西就是与一个数互质的数的和

但是我们只能求个数

考虑若\(gcd(i,n)=1\)，则\(gcd(n-i,n)=1\)

显然i一定成对出现

要特判一下1

所以，原式可以变为

\[n\sum_{d|n} \frac {\varphi(\lfloor\frac n d \rfloor)*\lfloor\frac n d \rfloor + 1} {2}
\]

这样最后的复杂度是\(O(T\sqrt n)\)的

不太好卡进去

因为时间浪费在了枚举因子

看到题目n的范围，显然可以开一个数组记录n的答案

这样是\(O(T+n\sqrt n)\)的

考虑枚举倍数，减少无用枚举

\(O(T+nlogn)\)可过

#include<bits/stdc++.h>

#define LL long long

LL in() {

	char ch; LL x = 0, f = 1;

	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);

	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));

	return x * f;

}

const int maxn = 1e6 + 10;

LL ans[maxn], phi[maxn], pri[maxn], tot;

bool vis[maxn];

LL getans(LL n) {

	return (phi[n] * n + 1) >> 1;

}

void predoit() {

	phi[1] = 1;

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

		if(!vis[i]) pri[++tot] = i, phi[i] = i - 1;

		for(int j = 1; j <= tot && (LL)i * pri[j] < maxn; j++) {

			vis[i * pri[j]] = true;

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

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

				break;

			}

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

		}

	}

	for(int i = 1; i < maxn; i++)

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

			ans[j] += getans(j / i);

}

int main() {

	predoit();

	for(int T = in(); T --> 0;) {

		LL n = in();

		printf("%lld\n", n * ans[n]);

	}

	return 0;

}

巴特西