Description

Input

Output

Sample Input

Sample Output

HINT

Source

分析：

$m \mod k+n \mod k>=k$可以转化为以下的式子...

$n-\left \lfloor \frac{n}{k} \right \rfloor*k+m-\left \lfloor \frac{m}{k} \right \rfloor*k>=k$

$n+m-k*( \left \lfloor \frac{n}{k} \right \rfloor+\left \lfloor \frac{m}{k} \right \rfloor )>=k$

$\left \lfloor \frac{n+m}{k} \right \rfloor-\left \lfloor \frac{n}{k} \right \rfloor-\left \lfloor \frac{m}{k} \right \rfloor>=1$

也就是$\left \lfloor \frac{n+m}{k} \right \rfloor-\left \lfloor \frac{n}{k} \right \rfloor-\left \lfloor \frac{m}{k} \right \rfloor=1$

$\sum_ {\left \lfloor \frac{n+m}{k} \right \rfloor-\left \lfloor \frac{n}{k} \right \rfloor-\left \lfloor \frac{m}{k} \right \rfloor=1} \phi(k)$

$=\sum_ {k=1}^{n+m} \phi(k)*\left\lfloor \frac{n+m}{k} \right \rfloor-\sum_ {k=1}^{n} \phi(k)*\left\lfloor \frac{n}{k} \right \rfloor-\sum_ {k=1}^{m} \phi(k)*\left\lfloor \frac{m}{k} \right \rfloor$

然后我们看$\sum_ {k=1}^{n} \phi(k)*\left\lfloor \frac{n}{k} \right \rfloor$是什么...

因为一个数的因子的欧拉函数之和为它本身...所以可以有以下的式子...

$\sum_ {k=1}^{n} \phi(k)*\left\lfloor \frac{n}{k} \right \rfloor=\sum_ {i=1}^{n} \sum_ {k\mid i} \phi(k)=\sum_ {i=1}^{n} i$

那么答案就是$\phi(n)*\phi(m)*n*m$...

代码：

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>//by NeighThorn#define int long longusing namespace std;int n,m,mod=998244353;inline int phi(int x){	int ans=x,y=sqrt(x);	for(int i=2;i<=y;i++)		if(x%i==0){			ans=ans/i*(i-1);			while(x%i==0)				x/=i;		}	if(x!=1)		ans=ans/x*(x-1);	return ans%mod;}signed main(void){	scanf("%lld%lld",&n,&m);	int ans=phi(n)*phi(m)%mod*(n%mod)%mod*(m%mod)%mod;	printf("%lld\n",ans);	return 0;}

By NeighThorn

BZOJ 4173: 数学