自动搬运

查看原文

来自洛谷，原作者为

	gcx12012 每一个不曾起舞的日子，都是对生命的辜负。

搬运于2025-08-24 23:16:55，当前版本为作者最后更新于2025-06-19 12:15:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

这种题也能想很久，彻底没救了。

Solution

由于不同质数之间都是相互独立的，我们可以先考虑一个质数的情况。

设 $m=p^k$，当其变成 $p^{k+1}$ 时，$\phi(m^2)$ 会发生什么变化。

我们发现，若 $k=0$，则 $\phi(m)$ 乘上 $p(p-1)$；否则它会乘上 $p^2$。

然后我们考虑将 $a,b$ 做质数拆分，然后从大到小考虑质数。设 $a$ 有 $k_1$ 个质因子 $p$，$b$ 有 $k_2$ 个质因子 $p$，那么我们按照 $|k_1-k_2|$ 的奇偶性讨论，如果为偶数则小的一边答案乘上 $p$，大的一边答案乘上 $p^{\frac{|k_1-k_2|}{2}+1}$；否则让大的一边答案乘上 $p^{\frac{|k_1-k_2|-1}{2}+1}$，然后把 $p-1$ 的质数拆分贡献到小的一边，一直这样做下去就做完了。

const ll V=10000;
ll cnt[N],cnt2[N];
ll a,b,m=1,n=1;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}


int main()
{
    //freopen("gcx.in","r",stdin);
    //freopen("gcx.out","w",stdout);
    a=read(),b=read();
    For(i,2,sqrt(a)){
        while(a%i==0) cnt[i]++,a/=i;
    }
    if(a>1) cnt[a]++;
    For(i,2,sqrt(b)){
        while(b%i==0) cnt2[i]++,b/=i;
    }
    if(b>1) cnt2[b]++;
    Rof(i,V,2){
        ll now=min(cnt[i],cnt2[i]);
        cnt[i]-=now,cnt2[i]-=now;
        if(cnt[i]){
            if(cnt[i]&1){
                For(j,1,cnt[i]/2+1) m*=i;
                ll now=i-1;
                For(j,2,sqrt(now)){
                    while(now%j==0) cnt2[j]++,now/=j;
                }
                if(now>1) cnt2[now]++;
            }else{
                m*=i,n*=i;
                For(j,1,cnt[i]/2) m*=i;
            }
        }
        if(cnt2[i]){
            if(cnt2[i]&1){
                For(j,1,cnt2[i]/2+1) n*=i;
                ll now=i-1;
                For(j,2,sqrt(now)){
                    while(now%j==0) cnt[j]++,now/=j;
                }
                if(now>1) cnt[now]++;
            }else{
                m*=i,n*=i;
                For(j,1,cnt2[i]/2) n*=i;
            }
        }
    }
    cout<<m<<' '<<n<<endl;
   	return 0;
}