洛谷 P3768 简单的数学题

https://www.luogu.org/problemnew/show/P3768

化简一下式子，就是$\sum_{d=1}^ncalc(d)d^2\varphi(d)$

其中$calc(d)=\frac{({\lfloor}\frac{n}{d}{\rfloor}+1)^2{{\lfloor}\frac{n}{d}{\rfloor}}^2}{4}$

可以对calc(d)做整除分块，那么要求$d^2\varphi(d)$的前缀和

看一眼数据范围，大概要杜教筛

凑了一会，发现令$f(d)=d^2\varphi(d)$，$g(d)=d^2$，$h=f*g$，那么$h(n)=n^2\sum_{d|n}\varphi(d)=n^3$

（也就是说$id^3=id^2\varphi*id^2$，好神奇啊）

那么就好办了，$n^3$的前缀和是有公式的（$1^3+2^3+..+n^3=(1+2+..+n)^2$）

杜教筛那个式子套一下就行了。。也可以预处理一点前缀和

复杂度？...不会算

以下是瞎扯：

设预处理1-K

算一次x，复杂度是$f(x)=\sum_{i=1}^{x/K}\sqrt{\frac{x}{i}}=O(\frac{x}{\sqrt{K}})$

后半部分复杂度是$\sum_{i=1}^{n/K}f(\frac{n}{i})=nK^{-\frac{1}{2}}\sum_{i=1}^{n/K}\frac{1}{i}=nK^{-\frac{1}{2}}log(n/K)$

总复杂度是$nK^{-\frac{1}{2}}log(n/K)+K$

当$K=n^{\frac{2}{3}}$时，复杂度是$n^{\frac{2}{3}}log$

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<map>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 ll md;

 ll H(ll n)

 {

     __int128 t=__int128(n+)*n/%md;

     return t*t%md;

 }

 ll G(ll n)

 {

     return __int128(n)*(n+)*(*n+)/%md;

 }

 ll Mod(ll n,ll d=md)

 {

     if(n>=)    return n%d;

     else if(n%d==)    return ;

     else    return d+n%d;

 }

 const ll K=;

 ll HH[K+],prime[K+],len;

 bool nprime[K+];

 map<ll,ll> ma;

 ll calc(ll n)

 {

     if(n<=K)    return HH[n];

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

     ll i,j,ans=H(n);

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

     {

         j=n/(n/i);

         ans=Mod(ans-Mod(G(j)-G(i-))*calc(n/i)%md);

     }

     return ma[n]=ans;

 }

 ll n;

 ll X(ll d)

 {

     __int128 t=__int128(n/d+)*(n/d)/%md;

     return t*t%md;

 }

 ll ans;

 int main()

 {

     ll i,j;

     //md=1000000007;

     scanf("%lld%lld",&md,&n);

     HH[]=;

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

     {

         if(!nprime[i])        {prime[++len]=i;HH[i]=i-;}

         for(j=;j<=len&&i*prime[j]<=K;j++)

         {

             nprime[i*prime[j]]=;

             if(i%prime[j]==)

             {

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

                 break;

             }

             else

                 HH[i*prime[j]]=HH[i]*(prime[j]-);

         }

     }

     for(i=;i<=K;i++)    HH[i]=HH[i]*i%md*i%md;

     for(i=;i<=K;i++)    HH[i]=(HH[i-]+HH[i])%md;

 //    while(1)

 //    {

 //        scanf("%lld",&n);

 //        printf("%lld\n",calc(n));

 //    }

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

     {

         j=n/(n/i);

         ans=(ans+X(i)*Mod(calc(j)-calc(i-))%md)%md;

     }

     printf("%lld",ans);

     return ;

 }

巴特西

洛谷 P3768 简单的数学题

最新文章

热门文章