题意

http://acm.hdu.edu.cn/showproblem.php?pid=6706

思考

打表出奇迹。

注意到这个式子有一大堆强条件限制，最后化为：

$$\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}{|i-j|*[(i,j)==1]}$$

考虑莫比乌斯反演：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}{|i-j|}$$

$$=\sum_{i=1}^{n}\sum_{j=1}^{n}{|i-j|}\sum_{d|i,d|j}{\mu(d)}$$
$$=\sum_{d=1}^{n}{\mu(d)*d*\sum_{i=1}^{\frac{n}{d}}\sum_{j-1}^{\frac{n}{d}}1}$$
$$=\sum_{d=1}^{n}{\mu(d)*d*F(\frac{n}{d})}$$

F是容易计算的。也就是说，我们要算出$\sum_{d=1}^{n}{\mu(d)*d}$在根号个点处的前缀和。杜教筛即可。

对于小于等于$10^6$的情况，线性筛预处理。

代码

 #pragma GCC optimize 2

 #include<bits/stdc++.h>

 #define mod 1000000007

 #define G2 500000004

 #define G3 333333336

 #define G6 166666668

 using namespace std;

 typedef long long int ll;

 const int maxn=1E6+;

 ll T,n,m;

 ll size,prime[maxn],mu[maxn],sum[maxn];

 ll F[maxn],f[maxn];

 int TOT;

 int used[maxn];

 bool vis[maxn];

 ll sqr,what[maxn];

 inline int where(int x)

 {

     return x<=sqr?x:n/x+sqr;

 }

 int gcd(int x,int y)

 {

     if(y==)

         return x;

     return x%y==?y:gcd(y,x%y);

 }

 inline ll qpow(ll x,ll y)

 {

     ll ans=,base=x;

     while(y)

     {

         if(y&)

             ans=ans*base%mod;

         base=base*base%mod;

         y>>=;

     }

     return ans;

 }

 inline ll G(ll m)

 {

     return (m*m%mod*(m-)%mod-m*(m-)%mod*(*m-)%mod*G3%mod+mod)%mod;

 }

 void init()

 {

     mu[]=;

     f[]=;

     F[]=;

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

     {

         if(!vis[i])

             prime[++size]=i,mu[i]=-,f[i]=i-;

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

         {

             vis[prime[j]*i]=;

             mu[prime[j]*i]=-mu[i];

             f[prime[j]*i]=f[i]*f[prime[j]]%mod;

             if(i%prime[j]==)

             {

                 mu[prime[j]*i]=;

                 f[prime[j]*i]=f[i]*prime[j]%mod;

                 break;

             }

         }

         F[i]=(F[i-]+f[i]*(ll)i%mod)%mod;

     }

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

         sum[i]=sum[i-]+mu[i]*(ll)i;

 }

 void small()

 {

     cout<<(F[n]-+mod)*G2%mod<<endl;

 }

 ll calc(ll n)

 {

     if(used[where(n)]==TOT)

         return what[where(n)];

     if(n<=)

         return what[where(n)]=sum[n];

     ll g=;

     for(ll l=,r;l<=n;l=r+)

     {

         r=n/(n/l);

         g=(g-(r-l+)*(r+l)%mod*G2%mod*calc(n/l)%mod+mod)%mod;

     }

     used[where(n)]=TOT;

     return what[where(n)]=g;

 }

 inline ll getsum(int x)

 {

     if(x<=)

         return sum[x];

     return what[where(x)];

 }

 void big()

 {

     ++TOT;

     sqr=sqrt(n+0.5);

     ll GG=calc(n);

     ll ans=;

     for(int l=,r;l<=n;l=r+)

     {

         r=n/(n/l);

         ans=(ans+(getsum(r)-getsum(l-)+mod)*G(n/l)%mod)%mod;

     }

     cout<<ans*G2%mod<<endl;

 }

 void solve()

 {

     ll a,b;

     cin>>n>>a>>b;

     if(n<=)

         small();

     else

         big();

 }

 int main()

 {

     ios::sync_with_stdio(false);

     init();

     cin>>T;

     while(T--)

         solve();

     return ;

 }

巴特西

[CCPC2019 ONLINE]E huntian oy

题意

思考

代码

最新文章

热门文章