Mertens

题意：

求解$\sum_{i=a}^b{\mu(i)}$。

解法：

由$(\mu * I)(n) = e(n)$ 得 $\sum_{d|n}{\mu(d)} = [n=1]$ 得 $\mu(n) = \sum_{d|n,d<n}{\mu(d)}$

从而有$$\sum_{i=1}^n{\mu(i)} = 1 - \sum_{i=1}^n{ \sum_{d|i,d<i}{\mu(d)} }$$

　　　　$$=1-\sum_{t=2}^n{ \sum_{d=1}^{[\frac{n}{t}]}{\mu(d)} }$$

记$S(n) = \sum_{i=1}^n{\mu(i)}$

从而有$S(n) = 1- \sum_{t=2}^n{S([\frac{n}{t}])}$

考虑分块优化此式，产生$O(\sqrt n)$的时间复杂度，当n小于等于$n^{0.6667}$时直接应用线性筛计算。

分析得会产生$O(n^{0.667})$个n，从而应用map，递归计算即可。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <ctime>

 #include <map>

 #define LL long long

 #define LIM 5000000

 using namespace std;

 int tot,prime[LIM+];

 LL u[LIM+];

 bool v[LIM+];

 map<LL,LL> ansv;

 LL S(LL n)

 {

     if(n<=LIM) return u[n];

     if(ansv.count(n)) return ansv[n];

     LL j;

     LL ans=;

     for(LL i=;i<=n;i=j+)

     {

         j=n/(n/i);

         ans -= (j-i+1LL) * S(n/i);

     }

     ansv[n]=ans;

     return ans;

 }

 int main()

 {

 //    freopen("test.txt","r",stdin);

     u[]=;

     for(int i=;i<=LIM;i++)

     {

         if(!v[i])

         {

             prime[++tot]=i;

             u[i]=-;

         }

         for(int j=;i*prime[j]<=LIM;j++)

         {

             v[i*prime[j]]=;

             u[i*prime[j]]=u[i]*u[prime[j]];

             if(i%prime[j]==)

             {

                 u[i*prime[j]]=;

                 break;

             }

         }

     }

     for(int i=;i<=LIM;i++) u[i]+=u[i-];

     LL a,b;

     cin >> a >> b;

     cout << S(b)-S(a-) << endl;

     return ;

 }

同样的方法，由$(\phi * I)(n) = id(n)$得到

$S(n) = \frac{n(n+1)}{2} - \sum_{t=2}^n{S([\frac{n}{t}])}$

注意n*(n+1)可能炸long long。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <ctime>

 #include <map>

 #include <cassert>

 #define LL long long

 #define LIM 5000000

 #define P 1000000007LL

 using namespace std;

 int tot,prime[LIM+];

 LL phi[LIM+],inv2;

 bool v[LIM+];

 map<LL,LL> ansv;

 LL S(LL n)

 {

     if(n<=LIM) return phi[n];

     if(ansv.count(n)) return ansv[n];

     LL j;

     LL ans=n%P * (n%P + 1LL) %P * inv2%P;

     assert(ans >=);

     for(LL i=;i<=n;i=j+)

     {

         j=n/(n/i);

         ans += P - ((j-i+1LL) * S(n/i)%P);

         if(ans>=P) ans -= P;

     }

     ansv[n]=ans;

     return ans;

 }

 LL qpow(LL x,int n)

 {

     LL ans=;

     for(;n;n>>=,x=x*x%P) if(n&) ans=ans*x%P;

     return ans;

 }

 int main()

 {

 //    freopen("test.txt","r",stdin);

     phi[]=;

     for(int i=;i<=LIM;i++)

     {

         if(!v[i])

         {

             prime[++tot]=i;

             phi[i]=i-;

         }

         for(int j=;i*prime[j]<=LIM;j++)

         {

             v[i*prime[j]]=;

             phi[i*prime[j]]=phi[i]*phi[prime[j]];

             if(i%prime[j]==)

             {

                 phi[i*prime[j]]=phi[i]*prime[j];

                 break;

             }

         }

     }

     inv2=qpow(,P-);

     for(int i=;i<=LIM;i++)

     {

         phi[i]=phi[i]+phi[i-];

         if(phi[i]>=P) phi[i] -= P;

     }

     LL n;

     cin >> n;

     cout << S(n) << endl;

     return ;

 }

巴特西

Mertens

最新文章

热门文章