「BZOJ4173」数学

「BZOJ4173」数学

题目大意：

求

[varphi(n) cdot varphi(m) cdot sum_{k in S(n,m)} varphi(k)quad mathrm{mod} quad 998244353 ]

其中 (S(n,m)) 为满足 $ mquad mathrm{mod} quad k + nquad mathrm{mod} quad k ge k$ 的 (k) 的集合。

我们可以对 $ mquad mathrm{mod} quad k + nquad mathrm{mod} quad k ge k$ 进行化简。

[m-lfloor frac{m}{k} floor*k + n-lfloor frac{n}{k} floor*k ge k \ m+n ge k(1+lfloor frac{m}{k} floor + lfloor frac{n}{k} floor) \ lfloor frac{m+n}{k} floor -lfloor frac{m}{k} floor - lfloor frac{n}{k} floor= 1\ ]

即 $ mquad mathrm{mod} quad k + nquad mathrm{mod} quad k ge k iff lfloor frac{m+n}{k} floor -lfloor frac{m}{k} floor - lfloor frac{n}{k} floor= 1$

令 (t=sum_{k in S(n,m)} varphi(k))

则

[t= sum_{k=1}^{n+m} varphi(k) cdot [ lfloor frac{m+n}{k} floor -lfloor frac{m}{k} floor - lfloor frac{n}{k} floor ] \ =sum_{k=1}^{n+m} varphi(k) cdot lfloor frac{m+n}{k} floor -sum_{k=1}^{m}varphi(k) cdotlfloor frac{m}{k} floor - sum_{k=1}^{n}varphi(k) cdotlfloor frac{n}{k} floor \ ]

考虑求解 (sum_{k=1}^{Q}varphi(k)cdotlfloor frac{Q}{k} floor)

则其等于

[sum_{k=1}^{Q}varphi(k)cdotlfloor frac{Q}{k} floor\ =sum_{k=1}^{Q} sum_{t=1}^{t le lfloor frac{Q}{k} floor} varphi(k)\ =sum_{t=1}^{Q} sum_{k|t} varphi(k)\ =sum_{t=1}^{Q} t ]

于是有 (ans= varphi(n) cdot varphi(m) cdot n cdot m)

时间复杂度 (O(sqrt{n}))

贴代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=998244353;
ll eular(ll n){
	ll ans=n;
	ll i=2;
	while(i*i<=n){
		if(n%i==0){
			while(n%i==0) n/=i;
			ans=ans/i*(i-1); 
		}
		++i;
	}
	if(n!=1) ans=ans/n*(n-1);
	return ans%p;
} 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	ll n,m;
	cin>>n>>m;
	cout<<(n%p*(m%p)%p*eular(n)%p*eular(m)%p)%p;
	return 0;
}