记录编号	531983	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[UVA 11426] [济南集训 2017] 求gcd之和	最终得分	100
用户昵称	ziiidan	是否通过	通过
代码语言	C++	运行时间	1.711 s
提交时间	2019-05-22 16:21:04	内存使用	166.25 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#define MOD 998244353

using namespace std;

const int maxn=1e7+10;

int n,m,cnt;
long long ans;
long long phi[maxn],prime[maxn];

void solve()
{
	phi[1]=1;
	for(register int i=2;i<=n;i++)
	{
		if(!phi[i]) phi[i]=i-1,prime[++cnt]=i;
		for(register int j=1;j<=cnt&&i*prime[j]<=n;j++)
		{
			if(i%prime[j]==0)
			{	
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
		
	}
}

int main()
{
	freopen("hoip.in","r",stdin);
	freopen("hoip.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(n>m) swap(n,m);
	solve();
	for(register int i=1;i<=n;i++) ans=(ans+(phi[i]%MOD*(n/i)%MOD)*(m/i)%MOD)%MOD;
	printf("%d\n",ans);
	return 0;
}