51nod 1227 平均最小公倍数 原题链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1227
A(n)=1n∑i=1nlcm(i,n)
∑k=1nA(k)=∑k=1n1k∑i=1klcm(i,k)=∑k=1n1k∑i=1kkigcd(i,k)=∑k=1n∑i=1kigcd(i,k)=∑k=1n∑d|k∑i=1kid[gcd(i,k)=d]=∑k=1n∑d|k∑i=1kdi[i⊥kd]
对于计算 [1,n] 与n互素的数字之和可以类比等差数列的倒叙相加。
因为a⊥n则： (n?a)⊥n
所以： ∑i=1n[i⊥n]i=φ(n)?n2
特别的， n=1 时： ∑i=1n[i⊥n]i=φ(n)?n+12
所以： ∑k=1n∑d|k∑i=1kdi[i⊥kd]=∑k=1n(12+∑d|kφ(d)d2)=n2+12∑d=1nφ(d)d?nd?
令： g(n)=φ(n)nidk(n)=nk
显而下面的狄利克雷积成立： g?id1=id2
f 的前缀和为： Sf
则： Sg(n)=n(n+1)(2n+1)6?∑i=2niSg(?ni?)
那么对于： ∑d=1nφ(d)d?nd?=∑L=1m?1L(Sg(?nL?)?Sg(?nL+1?))+∑d=1?nm?g(d)?nd?
【刷题小结|51nod 1227 平均最小公倍数】代码：
#include
#include
#include
#include
#define MAXN 1000000
#define SQR 40000
#define S(a) ((LL)(a)*((a)+1)%P*Iv[2]%P)
using namespace std;
typedef long long LL;
const int P=1e9+7;
int tmp[SQR];
int g[MAXN];
int phi[MAXN];
int Iv[SQR];
void init ()
{
Iv[1]=1;
for(int i=2;
i%i]*(P/i)%P)%P;
for(int i=1;
i=P)g[i]-=P;
}
}void clat(int n,int d)
{
int m=sqrt(n)+1,ans=0;
for(int L=1;
L=P)ans-=P;
}
for(int i=n/m;
i>1;
i--)
{
int u=n/i;
if(u=P)ans-=P;
}
m=(LL)n*(n+1)%P*(2*n+1)%P*Iv[6]%P;
tmp[d]=(P+m-ans)%P;
}void sum(int n)
{
if(n=P)ans-=P;
}
for(int i=n/m;
i;
i--)
{
ans+=(LL)phi[i]*(n/i)%P;
if(ans>=P)ans-=P;
}
return ans;
}int main ()
{
init();
int a,b;
scanf("%d %d",&a,&b);
a--;
int A=solve(a);
int B=solve(b);
A=(LL)A*Iv[2]%P;
A+=(LL)a*Iv[2]%P;
if(A>=P)A-=P;
B=(LL)B*Iv[2]%P;
B+=(LL)b*Iv[2]%P;
if(B>=P)B-=P;
printf("%d\n",(B-A+P)%P);
return 0;
} 推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔