QOJ 11356 A Totient Quotient
2026-06-25
题目大意
已知:
ϕ(k)=i=1∏j[(pi−1)(piνpi(k)−1)]
其中 νp(x) 表示质数 p 在 x 的质因数分解中的指数(例如 ν2(48)=4,表示 48 中含有 4 个质因子 2)。
给定两个互质的正整数 a 和 b,需要找到唯一的一对正整数 (m,n),满足:
- ba=ϕ(n2)ϕ(m2),其中 ϕ 为欧拉函数;
- 对于任意质数 p,若 p 整除 mn,则 νp(m)=νp(n);
- gcd(m,n) 为无平方因子数(即不被任何质数的平方整除)。
条件 2 和 3 确保了 (m,n) 是满足等式的最小唯一解。
你需要输出这个唯一的 m 和 n。
数据范围:1≤a,b≤104,gcd(a,b)=1,且保证输出的 m,n 均小于 263。
题解
我们先将题目中的欧拉函数公式变成平方的形式:
ϕ(n2)ϕ(m2)=p∏p2νp(n)−1(p−1)[νp(n)>0]p2νp(m)−1(p−1)[νp(m)>0]
注意这里只有 νp>0 才能乘 p−1。
结合条件 2 和 3,容易发现:∀p,(νp(m),νp(n)) 只有以下两类情况(注意 m,n 互换后有对称的两种):
- 一个指数是 1,另一个指数大于 1。
- 一个指数是 0,另一个指数大于 0。
为了方便,我们指定第一个是 νp(m),另一个是 νp(n),两种情况对答案的贡献如下:
- 此时的比值为:p2k−1(p−1)p(p−1)=p2k−21
- 此时的比值为:p2k−1(p−1)1
容易发现,两种的区别是:第一种只贡献 p 的偶数次方;第二种贡献 p 的奇数次幂,并附带 p−1(或 p−11)。
有了这个,我们考虑把 ba 进行拆分,容易发现,如果 p 次数为偶数次,一定来源于 1,奇数次同理,具体还原流程可以参考下方代码中高亮部分。
这里有一个问题:由于奇数次一定会附带 p−1,这会导致大质数污染小质数,如 5−1=4=22,所以我们要从大到小枚举 p。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1e4+10;
LL a , b;
LL cnta[N] , cntb[N];
int main() {
scanf("%lld%lld" , &a , &b);
for(int i = 2 ; i*i <= a ; i ++)
while(a % i == 0) cnta[i] ++ , a /= i;
if(a > 1) cnta[a] ++;
for(int i = 2 ; i*i <= b ; i ++)
while(b % i == 0) cntb[i] ++ , b /= i;
if(b > 1) cntb[b] ++;
LL m = 1 , n = 1;
for(int i = 1e4 ; i >= 2 ; i --) {
LL x = min(cnta[i] , cntb[i]);
cnta[i] -= x;
cntb[i] -= x;
if(cnta[i] == cntb[i]) continue;
if(cnta[i]) {
if(cnta[i] % 2 == 0) {
m *= i; n *= i;
for(int j = 1 ; j <= cnta[i]/2 ; j ++)
m *= i;
} else {
for(int j = 1 ; j <= cnta[i]/2 + 1 ; j ++)
m *= i;
LL tmp = i-1;
for(int j = 2 ; j*j <= tmp ; j ++)
while(tmp % j == 0) cntb[j] ++ , tmp /= j;
if(tmp > 1) cntb[tmp] ++;
}
} else {
if(cntb[i] % 2 == 0) {
m *= i; n *= i;
for(int j = 1 ; j <= cntb[i]/2 ; j ++)
n *= i;
} else {
for(int j = 1 ; j <= cntb[i]/2 + 1 ; j ++)
n *= i;
LL tmp = i-1;
for(int j = 2 ; j*j <= tmp ; j ++)
while(tmp % j == 0) cnta[j] ++ , tmp /= j;
if(tmp > 1) cnta[tmp] ++;
}
}
}
printf("%lld %lld\n" , m , n);
return 0;
}