N,M<=10^15
题解：一看就是一个推式子的题。。
首先把条件变形一下，把取模换成整除。
然后不等式两边都除个k.
再稍微分析一下。把不等号变成等号
就是 (n+m)/k=n/k+m/k+1;
然后把这个东西带入到原式子(先不管前面两项)。
就是
sigma(k)phi(k)*(n+m)/k(1<=k<=n+m)-sigma(k)phi(k)*n/k(1<=k<=n)-sigma(k)phi(k)*m/k(1<=k<=m)
sigma(k)phi(k)*x/k(1<=k<=x)可以化成sigma(t)sigma(k)phi(k)(1<=t<=x,k|t);
又因为 sigma(t)phi(t)(t|n)=n;
所以就成了sigma(i)i(1<=i<=n+m)-sigma(i)i(1<=i<=n)-sigma(i)i(1<=i<=m)
用等差数列求和公式求一下在乘上phi(n)和phi(m)就好了。
最后的式子就是n*m*phi(n)*phi(m);
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#define P 998244353
using namespace std;
long long n,m,ans;
long long phi(long long x)
{
long long ans=x,m=x;
for (long long i=2;i<=sqrt(x);i++)
if (m%i==0){ans=ans/i*(i-1);while (m%i==0) m/=i;}
if (m>1) ans=ans/m*(m-1);
return ans;
}
int main()
{
cin>>n>>m;
ans=((n%P)*(m%P))%P*(phi(n)%P)%P*(phi(m)%P)%P;
cout<<ans<<endl;
}
转播
