[CCPC2019 ONLINE]E huntian oy

题意

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$的情况，线性筛预处理。

代码

  1 #pragma GCC optimize 2
  2 #include<bits/stdc++.h>
  3 #define mod 1000000007
  4 #define G2 500000004
  5 #define G3 333333336
  6 #define G6 166666668
  7 using namespace std;
  8 typedef long long int ll;
  9 const int maxn=1E6+5;
 10 ll T,n,m;
 11 ll size,prime[maxn],mu[maxn],sum[maxn];
 12 ll F[maxn],f[maxn];
 13 int TOT;
 14 int used[maxn];
 15 bool vis[maxn];
 16 ll sqr,what[maxn];
 17 inline int where(int x)
 18 {
 19     return x<=sqr?x:n/x+sqr;
 20 }
 21 int gcd(int x,int y)
 22 {
 23     if(y==0)
 24         return x;
 25     return x%y==0?y:gcd(y,x%y);
 26 }
 27 inline ll qpow(ll x,ll y)
 28 {
 29     ll ans=1,base=x;
 30     while(y)
 31     {
 32         if(y&1)
 33             ans=ans*base%mod;
 34         base=base*base%mod;
 35         y>>=1;
 36     }
 37     return ans;
 38 }
 39 inline ll G(ll m)
 40 {
 41     return (m*m%mod*(m-1)%mod-m*(m-1)%mod*(2*m-1)%mod*G3%mod+mod)%mod;
 42 }
 43 void init()
 44 {
 45     mu[1]=1;
 46     f[1]=1;
 47     F[1]=1;
 48     for(int i=2;i<=1000000;++i)
 49     {
 50         if(!vis[i])
 51             prime[++size]=i,mu[i]=-1,f[i]=i-1;
 52         for(int j=1;j<=size&&prime[j]*i<=1000000;++j)
 53         {
 54             vis[prime[j]*i]=1;
 55             mu[prime[j]*i]=-mu[i];
 56             f[prime[j]*i]=f[i]*f[prime[j]]%mod;
 57             if(i%prime[j]==0)
 58             {
 59                 mu[prime[j]*i]=0;
 60                 f[prime[j]*i]=f[i]*prime[j]%mod;
 61                 break;
 62             }
 63         }
 64         F[i]=(F[i-1]+f[i]*(ll)i%mod)%mod;
 65     }
 66     for(int i=1;i<=1000000;++i)
 67         sum[i]=sum[i-1]+mu[i]*(ll)i;
 68 }
 69 void small()
 70 {
 71     cout<<(F[n]-1+mod)*G2%mod<<endl;
 72 }
 73 ll calc(ll n)
 74 {
 75     if(used[where(n)]==TOT)
 76         return what[where(n)];
 77     if(n<=1000000)
 78         return what[where(n)]=sum[n];
 79     ll g=1;
 80     for(ll l=2,r;l<=n;l=r+1)
 81     {
 82         r=n/(n/l);
 83         g=(g-(r-l+1)*(r+l)%mod*G2%mod*calc(n/l)%mod+mod)%mod;
 84     }
 85     used[where(n)]=TOT;
 86     return what[where(n)]=g;
 87 }
 88 inline ll getsum(int x)
 89 {
 90     if(x<=1000000)
 91         return sum[x];
 92     return what[where(x)];
 93 }
 94 void big()
 95 {
 96     ++TOT;
 97     sqr=sqrt(n+0.5);
 98     ll GG=calc(n);
 99     ll ans=0;
100     for(int l=1,r;l<=n;l=r+1)
101     {
102         r=n/(n/l);
103         ans=(ans+(getsum(r)-getsum(l-1)+mod)*G(n/l)%mod)%mod;
104     }
105     cout<<ans*G2%mod<<endl;
106 }
107 void solve()
108 {
109     ll a,b;
110     cin>>n>>a>>b;
111     if(n<=1000000)
112         small();
113     else
114         big();
115 }
116 int main()
117 {
118     ios::sync_with_stdio(false);
119     init();
120     cin>>T;
121     while(T--)
122         solve();
123     return 0;
124 }

View Code