- 求(phi(n) imesphi(m) imes sum_{n\%k+m\%kge k}phi(k))。
- (n,mle10^{15})
贡献转化+欧拉函数
考虑(n\%k+m\%kge k)充要于(lfloorfrac{n+m}k floor=lfloorfrac nk floor+lfloorfrac mk floor+1)。
因此我们实际上可以用((lfloorfrac{n+m}k floor-lfloorfrac nk floor-lfloorfrac mk floor) imesphi(k))来表示一个数(k)的贡献。
由此得出答案的计算式：
[phi(n) imesphi(m) imes(sum_{k=1}^{n+m}phi(k) imeslfloorfrac{n+m}k
floor-sum_{i=1}^nphi(k) imeslfloorfrac nk
floor-sum_{i=1}^mphi(k) imeslfloorfrac mk
floor)
]
(sum_{k=1}^nphi(k) imeslfloorfrac nk floor)其实是一个经典式子。根据(sum_{d|n}phi(d)=n)，我们发现：
[sum_{i=1}^ni=sum_{i=1}^nsum_{k|i}phi(k)=sum_{k=1}^nphi(k) imeslfloorfrac nk
floor
]
所以原式就等价于：
[phi(n) imesphi(m) imes(sum_{i=1}^{n+m}i-sum_{i=1}^ni-sum_{i=1}^mi)=phi(n) imesphi(m) imes nm
]
代码：(O(sqrt n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define LL long long
#define X 998244353
using namespace std;
LL n,m;I LL Phi(LL x)//求φ(x)
{
LL t=1;for(RI i=2;1LL*i*i<=x;++i) if(!(x%i)) {t*=i-1,x/=i;W(!(x%i)) t*=i,x/=i;}
return x^1&&(t*=x-1),t;
}
int main()
{
return scanf("%lld%lld",&n,&m),printf("%d
",(Phi(n)%X)*(Phi(m)%X)%X*(n%X)%X*(m%X)%X),0;
}