[杜教筛] 51Nod 1227 平均最小公倍数
糖老师博客传送门：http://blog.csdn.net/skywalkert/article/details/50500009
跟最小公倍数类似
求phi·id的前缀和 把phi卷上一个1
![[杜教筛] 51Nod 1227 平均最小公倍数](https://img.it610.com/image/info8/0feffe82617e4981873fcf68d6615081.png)
文章图片
【[杜教筛] 51Nod 1227 平均最小公倍数】
#include
#include
#include
#include
using namespace std;
using namespace std::tr1;
typedef long long ll;
const int P=1000000007;
const int inv2=(P+1)/2;
const int inv3=(P+1)/3;
const int maxn=5e6;
int prime[(int)1e6],num;
int vst[maxn+5],phi[maxn+5],sum[maxn+5];
inline void Pre(){
phi[1]=1;
for (int i=2;
i<=maxn;
i++){
if (!vst[i]) phi[i]=i-1,prime[++num]=i;
for (int j=1;
j<=num && (ll)i*prime[j]<=maxn;
j++){
vst[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 (int i=1;
i<=maxn;
i++) sum[i]=((ll)phi[i]*i%P+sum[i-1])%P;
}inline ll sum1(ll n){ return (n+1)%P*(n%P)%P*inv2%P;
}
inline ll sum2(ll n){ return (n%P)*((n+1)%P)%P*((2*n+1)%P)%P*inv2%P*inv3%P;
}
inline ll sum3(ll n){ return sum1(n)*sum1(n)%P;
}
inline ll sum1(ll l,ll r){ return (sum1(r)+P-sum1(l-1))%P;
}
inline ll sum2(ll l,ll r){ return (sum2(r)+P-sum2(l-1))%P;
}
inline ll sum3(ll l,ll r){ return (sum3(r)+P-sum3(l-1))%P;
}unordered_map S;
inline int Sum(ll n){
if (n<=maxn) return sum[n];
if (S.find(n)!=S.end()) return S[n];
int tem=sum2(n);
ll l,r;
for (l=2;
l*l<=n;
l++) (tem+=P-l%P*Sum(n/l)%P)%=P;
for (ll t=n/l;
l<=n;
l=r+1,t--)
r=n/t,(tem+=P-sum1(l,r)*Sum(t)%P)%=P;
return S[n]=tem;
}inline int Solve(ll n){
int tem=0;
ll l,r;
for (l=1;
l*l<=n;
l++) (tem+=Sum(n/l)%P)%=P;
for (ll t=n/l;
l<=n;
l=r+1,t--)
r=n/t,(tem+=(r-l+1)%P*Sum(t)%P)%=P;
tem=(ll)tem*inv2%P;
tem=(n%P*inv2%P+tem)%P;
return tem;
}int main(){
ll l,r;
freopen("t.in","r",stdin);
freopen("t.out","w",stdout);
Pre();
scanf("%lld%lld",&l,&r);
printf("%d\n",(Solve(r)+P-Solve(l-1))%P);
return 0;
}
推荐阅读
- Jieqian的ScalersTalk千人早起晨读团7期Day4复盘20181227
- 解题报告|51nod 1667 概率好题
- 水题纪念|【51nod - 1098】 最小方差（基础数学，公式化简，前缀和，积的前缀和）
- 51nod1616 最小集合(gcd 思维)
- NOJ|NOJ 1227: 拆数
- 杜教筛|hdu 6706 huntian oy 杜教筛
- 数论|HDU 6706 huntian oy(杜教筛)
- 数论|51Nod-1227-平均最小公倍数
- HDU6706|HDU6706 huntian oy(2019年CCPC网络赛+杜教筛)
- 51nod-1227-平均最小公倍数