题目描述

输入格式 Input Format

两个整数$N,M。N,M<={10}^{15}$

输出格式 Output Format

输出一个整数，表示满足条件的数.

输入：

5 6

输出：

240

---

想法

看起来根本不能做的题系列. . .
不过我们可以找规律嘛，打表输出20以内的所有(n,m)组合，就会发现所有满足要求的φ(k)的和其实等于n*m.
惊不惊喜，开不开心？
之后输出 $n\times m\times \varphi (n)\times \varphi (m)$ 即可.

嗯没错，这道题已经完了.

（再一次启示我们打表很重要,恩,没错

正规证法：

（我当时苦于证明的blog中的一歩，含神看了看说：这么简单,你乘法分配律怎么学的啊 ？然后我再看了一遍，*，把除号当成取余了QAQ

我们首先设$n\mathrm{\%}k=r_1,m\mathrm{\%}k=r_2;$
$n+m=(n/k+m/k)\ast k+r_1+r_2;$

呢么$(n+m)/k=n/k+m/k+(r_1+r_2)/k=n/k+m/k+1;$

所以$(n+m)/k-n/k-m/k=1;$

接下来就可以证：

(这公式真的打不出来QwQ)
所以$ sum = n m \phi(n)* \phi(m)$了。

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
long long phi(long long x)
{
	long long m=sqrt((double)x);
    long long k=x;
    for(long long i=2;i<=m;i++)
	{
        if(x%i==0)
		{
            k=k/i*(i-1);
            while(x%i==0)
				x/=i;
        }
    }
    if(x>1)
		k=k/x*(x-1);
    return k;
}
long long n,m;
int main()
{
	cin>>n>>m;
	cout<<(((n%998244353)*(m%998244353)%998244353)*((phi(n)%998244353)*(phi(m)%998244353)%998244353))%998244353<<endl;//注意必须每次乘都膜，wa了好几次QAQ
	return 0;
}
Copy