題意

求 \(\sum_{i=1}^nlcm(i,n)\) 。

傳送

Luogu

SPOJ

分析

原式可以化為

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

由于 \(gcd(i,n)=gcd(n-i,n)\) ，可將原式變形為

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

兩邊的 \(sum\) 對應相等，于是有

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

將 \(gcd(i,n)\) 相等的放在一起統計，枚舉 \(gcd(i,n)==d\) ，則 \(gcd(\frac{i}ze8trgl8bvbq,\frac{n}ze8trgl8bvbq)==1\) ，故 \(gcd(i,n)==d\) 的數量為 \(\varphi(\frac{n}ze8trgl8bvbq)\) 。

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

轉換枚舉順序，令 \(d'=\frac{n}ze8trgl8bvbq\) ，上式化為

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

設 \(g(n)=\sum_{d|n}\varphi(d)*d\) ，已知 \(g(n)\) 為積性函數，則可以預處理出答案，直接輸出即可。

代碼

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000000
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;template <typename T> inline void read(T &x) {T f = 1; x = 0; char c;for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);x *= f;
}int n;
ll ans[N+5];
int phi[N+5], prime[N+5];
bool vis[N+5];void get_phi() {int cnt = 0;phi[1] = 1;for (int i = 2; i <= N; ++i) {if (!vis[i]) prime[++cnt] = i, phi[i] = i - 1;for (int j = 1; j <= cnt && i * prime[j] <= N; ++j) {vis[i*prime[j]] = 1;if (i % prime[j] == 0) {phi[i*prime[j]] = phi[i] * prime[j];break;}phi[i*prime[j]] = phi[i] * (prime[j] - 1);}}
}void pre() {for (int i = 1; i <= N; ++i)for (int j = 1; j * i <= N; ++j)ans[i*j] += 1ll * j * phi[j] / 2;for (int i = 1; i <= N; ++i) ans[i] = 1ll * ans[i] * i + i;
}int main() {get_phi();pre();int t;read(t);while (t--) {read(n);printf("%lld\n", ans[n]);}return 0;
}

轉載于:https://www.cnblogs.com/hlw1/p/11562195.html

總結

以上是生活随笔為你收集整理的SP5971 LCMSUM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。