简单的数学题
题目描述
由于出题人懒得写背景了，题目还是简单一点好。
输入一个整数 \(n\) 和一个整数 \(p\)，你需要求出：
\[\left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p \]其中 \(\gcd(a,b)\) 表示 \(a\) 与 \(b\) 的最大公约数。
输入格式
一行两个整数 \(p,n\)。
输出格式
一行一个整数表示答案。
样例 #1
样例输入 #1
998244353 2000
样例输出 #1
883968974
提示
对于 \(20\%\) 的数据，\(n \leq 1000\)。
对于 \(30\%\) 的数据，\(n \leq 5000\)。
对于 \(60\%\) 的数据，\(n \leq 10^6\)，时限 1s。
对于另外 \(20\%\) 的数据，\(n \leq 10^9\)，时限 3s。
对于最后 \(20\%\) 的数据，\(n \leq 10^{10}\)，时限 4s。
对于 \(100\%\) 的数据，\(5 \times 10^8 \leq p \leq 1.1 \times 10^9\) 且 \(p\) 为质数。
\(\displaystyle\sum_{d=1}^{min(n,m)}\displaystyle\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\displaystyle\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ijd^3[gcd(i,j)=1]\)
\(\displaystyle\sum_{d=1}^{min(n,m)}d^3\displaystyle\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i\displaystyle\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}j[gcd(i,j)=1]\)
\(\displaystyle\sum_{d=1}^{min(n,m)}d^3\displaystyle\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i\displaystyle\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}j\displaystyle\sum_{e=1}^{min(i,j)}\mu(e)[e|i][e|j]\)
\(\displaystyle\sum_{d=1}^{min(n,m)}d^3\displaystyle\sum_{e=1}^{min(n,m)}\mu(e)e^2\displaystyle\sum_{i=1}^{\lfloor\frac{n}{de}\rfloor}i\displaystyle\sum_{j=1}^{\lfloor\frac{m}{de}\rfloor}j\)
设\(sum({\lfloor\frac{n}{de}\rfloor},{\lfloor\frac{m}{de}\rfloor})=\displaystyle\sum_{i=1}^{\lfloor\frac{n}{de}\rfloor}i\displaystyle\sum_{j=1}^{\lfloor\frac{m}{de}\rfloor}j\)，很容易算出。
原式\(=\displaystyle\sum_{d=1}^{min(n,m)}d^3\displaystyle\sum_{e=1}^{min(n,m)}\mu(e)e^2sum({\lfloor\frac{n}{de}\rfloor},{\lfloor\frac{m}{de}\rfloor})\)
只要能够快速计算\(\sum d^3\)和\(\sum\mu(e)e^2\)就可以了
可以发现两个都是积性函数，用杜教筛可以。
\(n\leq 1e10\)，两个整除分块，然后还要带一个杜教赛。。。真能过吗？
包过不了的。
\(gcd(i,j)=\displaystyle\sum_{k|i,k|j}\phi(k)\)
我草我才看到没有\(m\)，只有\(n\)。。那可以简化一下了
\(\displaystyle\sum_{d=1}^{n}d^3\displaystyle\sum_{e=1}^{\lfloor \frac n d\rfloor}\mu(e)e^2(\displaystyle\sum_{k=1}^{\lfloor\frac{n}{de}\rfloor}k)^2\)
总共有两个枚举因数的部分...是不是这样的话就可以简化？
令\(T=de\)
\(\displaystyle\sum_{T=1}^{n}(sum(\lfloor\frac n T\rfloor))^2\displaystyle\sum_{d|T}d^3(\frac T d)^2\mu(\frac T d)\)
\(\displaystyle\sum_{T=1}^{n}(sum(\lfloor\frac n T\rfloor))^2T^2\displaystyle\sum_{d|T}d\mu(\frac T d)\)
这个替换有点难理解。。我总感觉会漏东西。哦，其实先把\(d\)的部分和后面\(e\)的部分写在一起就好了
然后就是考虑怎么计算\(T^2\displaystyle\sum_{d|T}d\mu(\frac T d)\)，然后可以发现，后面的形式就是狄利克雷卷积的形式。其实后面的部分可以用这个改写。
用\(*\)表示狄利克雷卷积，那么\(T^2\displaystyle\sum_{d|T}d\mu(\frac T d)=T^2(id*\mu)(T)\)，熟悉的话其实就能够发现，\(id*\mu=\phi\)
那么后面的部分就变成了\(T^2\phi(T)\)。对于\(\displaystyle\sum_{d|T}\)这种东西要敏感，他在莫反里面其实很重要，虽然其实是狄利克雷卷积很好用。
只需要两个枚举因子的部分就能够产生出\(\displaystyle\sum_{d|T}\)，而莫反的题目，出现了\(gcd\)之后，两个枚举因子的循环的出现也是轻轻松松。所以更是能体现重要性
然后对于\(T^2\phi(T)\)，我们考虑直接用杜教筛筛出，观察杜教筛核心\(g(1)S(n)=\displaystyle\sum_{i=1}^n(f*g)(i)-\displaystyle\sum_{d=2}^ng(d)S({\lfloor\frac{n}{d}\rfloor})\)
我们所需要求的为\(S(n)=\sum f(i),f(i)=i^2\phi(i)\)，只需要保证\(f*g\)和任意一个\(g(i)\)容易得到即可。
直接构造\(g(i)=i^2\)，可以发现\((f*g)(i)=\displaystyle\sum_{d|i}\phi(d)d^2\times (\frac i d)^2=i^2*\displaystyle\sum_{d|i}\phi(d)=i^3\)，所以\(\displaystyle\sum_{i=1}^n(f*g)(i)=\displaystyle\sum_{i=1}^ni^3=(\displaystyle\sum_{i=1}^ni)^2\)
就能算了。
居然不用整除分块？
\(\displaystyle\sum_{T=1}^{n}(sum(\lfloor\frac n T\rfloor))^2T^2\phi(T)\)
哦要的，不然T了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
ll a=0,b=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
return a*b;
}
const ll N=7e6;
ll phi[N+1],prim[N+1],cnt,mu[N+1],n,p,Ned[N+1],inv2,inv6;
unordered_map<ll,ll> ans_mu,ans_phi,ans_Ned;
ll vis[N+1];
inline ll ksm(ll x,ll y)
{
if(y==1)return x;
if(y==0)return 0;
if(y%2==1)
{
ll now=ksm(x,y/2)%p;
return now*now%p*x%p;
}
else
{
ll now=ksm(x,y/2)%p;
return now*now%p;
}
}
ll Sum_mu(ll n)
{
if(n<=N)return mu[n];
if(ans_mu[n])return ans_mu[n];
ll ans=1;
for(ll l=2,r;l<=n;l=r+1)
{
r=n/(n/l);
ans-=1LL*(r-l+1)*(Sum_mu(n/l));
}
return ans_mu[n]=ans;
}
ll Sum_phi(ll n)
{
if(n<=N)return phi[n];
if(ans_phi[n])return ans_phi[n];
ll ans=(n+1)%p*(n)%p*inv2%p;
for(ll l=2,r;l<=n;l=r+1)
{
r=n/(n/l);
ans=(ans-(r-l+1)%p*Sum_phi(n/l)%p+p)%p;
}
return ans_phi[n]=ans%p;
}
ll Sum_g(ll n)
{
n%=p;
return (n)%p*(n+1)%p*(2*n+1)%p*inv6%p;
}
ll Sum_Ned(ll n)
{
if(n<=N)return Ned[n];
if(ans_Ned[n])return ans_Ned[n]%p;
ll Can=n%p;
ll ans=(Can+1)*Can/2%p;
ans=ans*ans%p;
for(ll l=2,r;l<=n;l=r+1)
{
r=(n/(n/l));
ans=(ans+p-((Sum_g(r)-Sum_g(l-1)+p)%p)*(Sum_Ned(n/l))%p)%p;
}
return ans_Ned[n]=ans%p;
}
void init()
{
mu[1]=phi[1]=1;//先用筛法算出较小的部分
for(ll i=2;i<=N;i++)
{
if(vis[i]==0)prim[++cnt]=i,mu[i]=-1,phi[i]=i-1;
for(ll j=1;j<=cnt&&prim[j]*i<=N;j++)
{
vis[prim[j]*i]=1;
if(i%prim[j]==0)
{
phi[i*prim[j]]=phi[i]*prim[j];
mu[i*prim[j]]=0;
break;
}
phi[i*prim[j]]=phi[i]*phi[prim[j]];
mu[i*prim[j]]=mu[i]*mu[prim[j]];
}
}
for(ll i=1;i<=N;i++)Ned[i]=phi[i]%p*i%p*i%p;
for(ll i=1;i<=N;i++)mu[i]+=mu[i-1],phi[i]=(phi[i]+phi[i-1])%p,Ned[i]=(Ned[i]+Ned[i-1])%p;
}
int main()
{
p=read(),n=read();
inv2=ksm(2,p-2)%p;
inv6=ksm(6,p-2)%p;
init();
ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ll Can=(n/l)%p;
ans+=((Can+1)*(Can)%p*inv2%p)*((Can+1)*(Can)%p*inv2%p)%p*((Sum_Ned(r)-Sum_Ned(l-1)+p)%p)%p;
// ans=(ans+((Can+1)*(Can)/2%p)*((Can+1)*(Can)/2%p)%p*((Sum_Ned(r)-Sum_Ned(l-1)+p)%p)%p)%p;
ans=ans%p;
// cout<<l<<endl;
}
cout<<ans<<endl;
return 0;
}
3个取模，硬控三天。
我草，这个真的是只能静态查，真的离谱。