专栏文章

题解：P12620 [NAC 2025] A Totient Quotient

ggcx12012
P12620题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip2gy4x
此快照首次捕获于
2025/12/03 05:04
3 个月前
此快照最后确认于
2025/12/03 05:04
3 个月前
查看原文

前言

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

Solution

由于不同质数之间都是相互独立的，我们可以先考虑一个质数的情况。
设 m=pkm=p^k，当其变成 pk+1p^{k+1} 时，ϕ(m2)\phi(m^2) 会发生什么变化。
我们发现，若 k=0k=0，则 ϕ(m)\phi(m) 乘上 p(p−1)p(p-1)；否则它会乘上 p2p^2。
然后我们考虑将 a,ba,b 做质数拆分，然后从大到小考虑质数。设 aa 有 k1k_1 个质因子 pp，bb 有 k2k_2 个质因子 pp，那么我们按照 ∣k1−k2∣|k_1-k_2| 的奇偶性讨论，如果为偶数则小的一边答案乘上 pp，大的一边答案乘上 p∣k1−k2∣2+1p^{\frac{|k_1-k_2|}{2}+1}；否则让大的一边答案乘上 p∣k1−k2∣−12+1p^{\frac{|k_1-k_2|-1}{2}+1}，然后把 p−1p-1 的质数拆分贡献到小的一边，一直这样做下去就做完了。
CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...