<span>题解「Luogu6055 [RC-02] GCD」</span>
题目要求：
\[\text{Ans}=\sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\lfloor\frac{N}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{N}{j}\rfloor}[{\rm{gcd}}(i,j)=1][{\rm{gcd}}(p,q)=1] \]
式中 \(p,q\) 的枚举范围均只与 \(j\) 有关，根据这个下取整的形式，想到下面这个常用的式子：
\[\sum_{i=1}^N\sum_{j=1}^N[{\rm{gcd}}(i,j)=k]=\sum_{k=1}^N\sum_{i=1}^{\lfloor\frac{N}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{N}{k}\rfloor}[{\rm{gcd}}(i,j)=1] \]
所以我们用 \(p,q\) 代替 \(jp,jq\) ，式子变为：
\[\begin{align} &\sum_{i=1}^N\sum_{p=1}^{N}\sum_{q=1}^{N}[{\rm{gcd}}(i,j)=1][{\rm{gcd}}(p,q)=j]\\ &=\sum_{i=1}^N\sum_{p=1}^{N}\sum_{q=1}^{N}[{\rm{gcd}}(i,{\rm{gcd}}(p,q))=1]\\ &=\sum_{i=1}^N\sum_{p=1}^{N}\sum_{q=1}^{N}[{\rm{gcd}}(i,p,q)=1]\\ &=\sum_{i=1}^N\sum_{p=1}^{N}\sum_{q=1}^{N}\sum_{d|i,d|p,d|q}\mu(d)\\ &=\sum_{d=1}^N\mu(d)\lfloor\frac{N}{d}\rfloor^3 \end{align} \]
杜教筛+整除分块即可。
\(\text{Code}:\)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#define maxn 10000005
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
const lxl mod=998244353;
template <typename T>
inline T read()
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int prime[maxn],cnt;
bool flag[maxn];
lxl mu[maxn];
inline void sieve()
{
mu[1]=1;
for(int i=2;i<maxn;++i)
{
if(!flag[i]) prime[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*prime[j]<maxn;++j)
{
flag[i*prime[j]]=true;
if(!(i%prime[j])) break;
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<maxn;++i)
mu[i]+=mu[i-1];
}
map<int,lxl> mp;
inline lxl GetS(int n)
{
if(n<maxn) return mu[n];
if(mp[n]) return mp[n];
lxl res=1;
for(int l=2,r;l<=n;l=r+1)
{
r=n/(n/l);
res=(res-(r-l+1)*GetS(n/l)%mod+mod)%mod;
}
return mp[n]=res;
}
inline lxl calcu(lxl N)
{
lxl res=0;
for(lxl l=1,r;l<=N;l=r+1)
{
r=N/(N/l);
lxl d=N/l;d=d*d%mod*d%mod;
res=(res+(GetS(r)-GetS(l-1)+mod)%mod*d%mod)%mod;
}
return res;
}
int main()
{
// freopen("P6055.in","r",stdin);
sieve();
lxl N=read<lxl >();
printf("%lld\n",calcu(N));
return 0;
}
理想汽车工作强度 73人发布