正題

P1891

---

題目大意

有T個(gè)詢問，每個(gè)詢問給出n，求$$\sum _{i=1}^{n}lcm(i,n)$$

---

解題思路

$$\sum _{i=1}^{n}lcm(i,n)$$
$$n\sum _{i=1}^{n}i/gcd(i,n)$$
$$n\sum _{d|n}\frac{1}{d}\sum _{i=1}^{n}i[gcd(i,n)=d]$$
對互質(zhì)的數(shù)求和
$$n\sum _{d|n}\frac{1}{d}\times \frac{\phi (\frac{n}{d})n}{2}$$
$$n\sum _{d|n}\frac{\phi (d)\times d}{2}$$

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 1000100 using namespace std; ll T,n,w,p[N],prime[N],phi[N],g[N]; const ll MX=1e6; void work() {phi[1]=1;for(ll i=2;i<=MX;++i){if(!p[i]){prime[++w]=i;phi[i]=i-1;}for(ll j=1;j<=w&&i*prime[j]<=MX;++j){p[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1);}}for(ll i=1;i<=MX;++i)for(ll j=1;i*j<=MX;++j)g[i*j]+=(i==1?1:i*phi[i]/2);//1只有一個(gè)數(shù)return; } int main() {work();scanf("%lld",&T);while(T--){scanf("%lld",&n);printf("%lld\n",n*g[n]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【数论】疯狂 LCM（P1891）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。