本文共 1078 字，大约阅读时间需要 3 分钟。
题目链接:
求 ∑ i = 1 n l c m ( n , i ) \sum_{i=1}^n lcm(n,i) i=1∑nlcm(n,i)
∑ i = 1 n l c m ( n , i ) \sum_{i=1}^n lcm(n,i) i=1∑nlcm(n,i)
∑ i = 1 n n i g c d ( n , i ) \sum_{i=1}^n \frac{ni}{gcd(n,i)} i=1∑ngcd(n,i)ni n ∑ d ∣ n ∑ i = 1 n [ ( n , i ) = = d ] i n\sum_{d\mid n}\sum_{i=1}^n[(n,i)==d]i nd∣n∑i=1∑n[(n,i)==d]i n ∑ d ∣ n ∑ i = 1 n [ ( n / d , i / d ) = = 1 ] i n\sum_{d\mid n}\sum_{i=1}^n[(n/d,i/d)==1]i nd∣n∑i=1∑n[(n/d,i/d)==1]i n ∑ d ∣ n d ∗ φ ( d ) 2 n\sum_{d|n}\frac{d*\varphi(d)}{2} nd∣n∑2d∗φ(d)然后预处理 O ( n log n ) O(n\log n) O(nlogn)然后 O ( 1 ) O(1) O(1)回答即可
时间复杂度 O ( n log n + T ) O(n\log n+T) O(nlogn+T)
#include#include #include #define ll long longusing namespace std;const ll N=1e6; ll T,phi[N+10],ans[N+10],n;int main(){ for (ll i=2;i<=N;i++) phi[i]=i; for (ll i=2;i<=N;i++) { bool flag=(phi[i]==i); for (ll j=i;j<=N;j+=i){ if(flag) phi[j]=phi[j]/i*(i-1); ans[j]+=phi[i]*i/2; } } scanf("%lld",&T); while(T--){ scanf("%lld",&n); printf("%lld\n",n*(ans[n]+1)); }}
转载地址：http://zkkaf.baihongyu.com/