[SPOJ LCMSUM]数论
发布者:edward_mj 5月 31, 2010 [SPOJ LCMSUM]数论有9条评论
求LCM(1,N)+LCM(2,N)+LCM(3,N)+...+LCM(N,N)
ans=n*(1/gcd(1,n)+2/gcd(2,n)+...+n/gcd(n,n))
其中显然gcd(x,n)都是n的约数.
然后我们都知道n的约数的个数是n^0.5级别的.
于是可以考虑把分母相同的合并.
然后设x为n的一个约数,那么(kx,n)=x 当且仅当满足 (k,n/x)=1
然后再有不等式kx<=n 即 k<=n/x.
k<=n/x (k,n/x)=1 想到了什么?
欧拉函数~
设t=n/x
但是现在要求