bzoj 4173: 数学 （数论+sqrt求phi）

Description

Input

 输入文件的第一行输入两个正整数 。 

Output

 如题

Sample Input

Sample Output

HINT

 N,M<=10^15

Source

题解：化式子（其实是可以找规律的嘛）+sqrt求phi

这道题找规律是个好方法，最后的答案就是phi(n)*phi(m)*m*n%p

但是还是需要知道应该知道推导。。。

n=x*k+r1,m=y*k+r2 

n%k=r1 n/k=x

m%k=r2 m/k=y

m+n=(x+y)*k+(r1+r2)

由r1+r2>=k推得(n+m)%k=r1+r2-k,(n+m)/k=q1+q2+1

所以floor((n+m)/k)-floor(n/k)-floor(m/k)=1,不满足条件的k对应的floor((n+m)/k)-floor(n/k)-floor(m/k)=0

然后我们在看一下式子 

sigma(k∈S)phi(k)=sigma(k=1..n+m) phi(k)*(floor((n+m)/k)-floor(n/k)-floor(m/k))

=simga(k=1..n+m)phi(k)*floor((n+m)/k)-sigma(k=1..n+m)phi(k)*floor(n/k)-sigma(k=1..n+m)phi(k)*floor(m/k)

如果k>m,floor(m)=0，n也是同理

进一步化简：simga(k=1..n+m)phi(k)*floor((n+m)/k)-sigma(k=1..n)phi(k)*floor(n/k)-sigma(k=1..m)phi(k)*floor(m/k)

接下来怎么搞呢？

sigma(k=1..n)i =sigma(k=1..n) sigma(i|k)phi(i)=sigma(i=1..n) phi(i)*floor(n/i)

然后发现，这个式子就是上面相似的三部分耶

所以式子最终化成：

sigma(k∈S)phi(k)=sigma(k=1..n+m)k-sigma(k=1..n)k-sigma(k=1..m)k

=n*m

phi(n)*phi(m)*sigma(k∈S)phi(k)=phi(n)*phi(m)*n*m%p 得证。

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define LL long long #define p 998244353using namespace std;LL n,m;LL phi(LL x){	LL k=x; LL ans=x;	for (LL i=2;i*i<=k;i++)	 if (k%i==0) {	 	ans=ans/i*(i-1);	 	while (k%i==0) k/=i;	 } 	if (k>1) ans=ans/k*(k-1);	return ans%p;}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%I64d%I64d",&n,&m);	LL ans=phi(n)*phi(m)%p; n%=p; m%=p;	PRintf("%I64d/n",ans%p*n%p*m%p);}