锐客网

  1. 首页 > it技术 > >

[51nod1227]平均最小公倍数（反演+杜教筛）

莫比乌斯反演

题目： 我是超链接
题解： A函数实际上是
1n∑i=1ningcd(i,n)=∑i=1nigcd(i,n)1 n ∑ i = 1 n i n g c d ( i , n ) = ∑ i = 1 n i g c d ( i , n )
那么我们要求的F函数就是 ∑i=1n∑j=1ijgcd(i,j)∑ i = 1 n ∑ j = 1 i j g c d ( i , j )
经过套路的画柿子之后我们得到的是 ∑d=1n∑i=1nd∑j=1i[(i,j)=1]j∑ d = 1 n ∑ i = 1 n d ∑ j = 1 i [ ( i , j ) = 1 ] j
我们发现j循环的这一堆似乎有意义：1..i内与i互质数的和
对于i与n互素，gcd(n,i)=1，则必有gcd(n,n-i)=1
设n的欧拉函数值为φ[n]，则有φ[n]个数与n互素，这些数两两相加必等于n
于是有答案为φ[n]*n/2，但对于n=1，我们要的输出是1，但根据这个意义来说是0，这样就导致i=1的没有计算，一共少算了n次，少了n，我们加上就是了，还有一个问题就是/2，我们一样拉到外面就行了
那么柿子又变得优美了
1/2?(n+∑d=1n∑i=1ndφ(i)?i)1 / 2 ? ( n + ∑ d = 1 n ∑ i = 1 n d φ ( i ) ? i )
后面这一堆怎么这么套路啊，杜教筛吧，那我们设 F(i)=φ(i)?iF ( i ) = φ ( i ) ? i，则我们要求 Sum(i)=∑ni=1F(i)S u m ( i ) = ∑ i = 1 n F ( i )
这个时候应该找一个前缀和好求的函数和F卷起来得到一个前缀和好求的函数，我们找到 h(i)=ih ( i ) = i

F?h(n)=∑d|nφ(d)?d?nd=n?∑d|nφ(d)=n2F ? h ( n ) = ∑ d | n φ ( d ) ? d ? n d = n ? ∑ d | n φ ( d ) = n 2
有戏了，接着画（有意识的让F(i)里面的i是可以递归求解的）
∑i=1ni2=∑i=1nF?h(i)=∑i=1n∑d|iF(id)?d=∑d=1nd∑i=1ndF(i)∑ i = 1 n i 2 = ∑ i = 1 n F ? h ( i ) = ∑ i = 1 n ∑ d | i F ( i d ) ? d = ∑ d = 1 n d ∑ i = 1 n d F ( i )
那么移个项就可以了

Sum(n)=∑i=1ni2?∑d=2nd?Sum(nd)S u m ( n ) = ∑ i = 1 n i 2 ? ∑ d = 2 n d ? S u m ( n d )
【[51nod1227]平均最小公倍数（反演+杜教筛）】完结撒花??ヽ(?▽?)ノ?
代码：

#include #include #include #define LL long long using namespace std; const int mod=1e9+7; const int maxn=1000000; const int N=1000050; int pri[N],tot; bool ss[N]; LL inv6,inv2,phi[N]; mapmp; LL pfh(LL a){a%=mod; return a*(a+1)%mod*(2*a+1)%mod*inv6%mod; } LL he(LL a){a%=mod; return a*(a+1)%mod*inv2%mod; } LL ksm(LL a,LL k) { LL ans=1; for (; k; k>>=1,a=a*a%mod) if (k&1) ans=ans*a%mod; return ans; } LL inv(LL a){a%=mod; return ksm(a,mod-2); } void init(int n) { phi[1]=1; for (int i=2; i<=n; i++) { if (!ss[i]) pri[++tot]=i,phi[i]=i-1; for (int j=1; j<=tot && pri[j]*i<=n; j++) { ss[pri[j]*i]=1; if (i%pri[j]==0) { phi[pri[j]*i]=(LL)pri[j]*phi[i]%mod; break; } phi[pri[j]*i]=(LL)(pri[j]-1)*phi[i]%mod; } } for (int i=1; i<=n; i++) phi[i]=(phi[i]*(LL)i%mod+phi[i-1])%mod; inv6=inv(6); inv2=inv(2); } LL Sum(int n) { if (n<=maxn) return phi[n]; if (mp.count(n)) return mp[n]; LL ans=pfh(n); for (int i=2,last; i<=n; i=last+1) { last=n/(n/i); ans=(ans-(LL)(he(last)-he(i-1))%mod*Sum(n/i)%mod+mod)%mod; } return mp[n]=ans; } LL solve(int n) { LL ans=0; for (int i=1,last; i<=n; i=last+1) { last=n/(n/i); ans=(ans+(LL)(last-i+1)*Sum(n/i)%mod)%mod; } return (ans+n)%mod*inv2%mod; } int main() { int a,b; scanf("%d%d",&a,&b); init(min(b,maxn)); printf("%lld",(solve(b)-solve(a-1)+mod)%mod); }

    推荐阅读


    上一篇：windows下信号量和共享内存api， mark:共享内存实现进程间锁

    下一篇：【回忆】至暗时刻