正題

題目鏈接:http://www.51nod.com/Challenge/Problem.html#problemId=1227

---

題目大意

定義
$$F(a)=\frac{{\sum }_{i=1}^{a}lcm(a,i)}{a}$$
給出$l,r$求${\sum }_{i=l}^{r}F(i)$

---

解題思路

好久沒(méi)做數(shù)論題了
直接拆成兩個(gè)前綴和的差，然后有
$$\sum _{i=1}^n\sum _{j=1}^i\frac{j}{gcd(i,j)}$$
$$\sum _{d=1}^n\frac{1}{d}\sum _{i=1}^n\sum _{j=1}^{i}j[gcd(i,j)=d]$$
$$\sum _{d=1}^n\sum _{i=1}^{?\frac{n}{d}?}\sum _{j=1}^{i}j[gcd(i,j)=1]$$
$$\frac{1}{2}+\sum _{d=1}^n\sum _{i=1}^{?\frac{n}{d}?}\frac{\phi (i)i}{2}$$

函數(shù)$H(n)=\phi (n)n$可以用杜教篩，$H\times id$就可以得到$n^2$的函數(shù)。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<map> #define ll long long using namespace std; const ll N=5e6,P=1e9+7; ll cnt,pri[N/10],phi[N]; bool v[N];map<ll,ll> mp; void Prime(){phi[1]=1;for(ll i=2;i<N;i++){if(!v[i])pri[++cnt]=i,phi[i]=i-1;for(ll j=1;j<=cnt&&i*pri[j]<N;j++){v[i*pri[j]]=1;if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}phi[i*pri[j]]=phi[i]*(pri[j]-1);}}for(ll i=1;i<N;i++)phi[i]=(phi[i]*i+phi[i-1])%P;return; } ll GetS(ll n) {return n*(n+1)/2%P;} ll GetSS(ll n) {return n*(n+1)%P*(2*n+1)%P*((P+1)/6)%P;} ll GetPhi(ll n){if(n<N)return phi[n];if(mp[n])return mp[n];ll ans=GetSS(n);for(ll l=2,r;l<=n;l=r+1){r=n/(n/l);(ans-=GetPhi(n/l)*(GetS(r)-GetS(l-1))%P)%=P;}mp[n]=ans;return ans; } ll solve(ll n){ll ans=0;if(!n)return 0;for(ll l=1,r;l<=n;l=r+1){r=n/(n/l);(ans+=(GetPhi(n/l)+1)*(r-l+1)%P)%=P;}return ans*((P+1)/2)%P; } signed main() {ll l,r,ans;Prime();scanf("%lld%lld",&l,&r);ans=(solve(r)-solve(l-1))%P;printf("%lld\n",(ans+P)%P);return 0; }

總結(jié)

以上是生活随笔為你收集整理的51nod1227-平均最小公倍数【杜教筛,欧拉函数】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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