BZOJ 4173: 数学

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 long
using 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: 数学

原文：http://www.cnblogs.com/neighthorn/p/6413808.html