没有任何思路，打表发现ans=phi(n)*phi(m)*n*m
%%% popoqqq Orz
然而并没有看懂……
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define mod 998244353ll
using namespace std;
long long getphi(long long x){
long long ans=x;
for(long long i=2;i*i<=x;i++)
if(x%i==0){
ans/=i;ans*=i-1;
while(x%i==0)x/=i;
}
if(x!=1){ans/=x;ans*=x-1;}
return ans;
}
int main(){
long long n,m,x,y,ans=1;
scanf("%lld%lld",&n,&m);
x=getphi(n)%mod;
y=getphi(m)%mod;
n%=mod; m%=mod;
ans=n;ans=(ans*m)%mod;
ans=(ans*x)%mod;ans=(ans*y)%mod;
printf("%lld\n",ans);
return 0;
}附打表程序
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 500
using namespace std;
int phi[N],prime[N],tot;
bool bo[N];
void init(){
phi[1]=1;
for(int i=2;i<=N;i++){
if(!bo[i]){
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*prime[j]<=N;j++){
bo[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
void work(int x,int y){
int cnt=0;
printf("phi[%d]==%d phi[%d]==%d\n",x,phi[x],y,phi[y]);
for(int i=2;i<=x+y;i++)
if(x%i+y%i>=i){
printf("phi[%d]==%d\n",i,phi[i]);
cnt+=phi[i];
}
printf("%d %d %d %d ans==%d\n",x,y,phi[x],phi[y],phi[x]*phi[y]*cnt);
}
int main(){
int x,y;
init();
while(scanf("%d%d",&x,&y)==2)
work(x,y);
}