题解：P12620 [NAC 2025] A Totient Quotient

· · 题解

前言

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

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;
}