题目要求：

\[\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;
}