1.分析
我们要求的是:(p/q)^k (p/q)>1,所以使k最大,即求 α1~α(N-1)的最大公约数
这里我们使用更相减损术,因为我们没有得到确切的α1~α(N-1)是多少,我们只有(p/q)^α1,(p/q)^α2,...,(p/q)^α(N-1)这些的值
上图p/q不能再拆分成次幂的理解(可不是p或q不可以继续拆分)
上图p/q的k次方k的限制
可以看出k是每一个αi的约数,那么答案就是求所有αi的最大公约数
2.辗转相减法(更相减损术)与辗转相除法的对比以及实现过程
//更相减损术总用较大的减去较小的
/*例子:
a b a-b
98 - 63 = 35
63 - 35 = 28
35 - 28 = 7
28 - 7 = 21
21 - 7 = 14
14 - 7 = 7
7 - 7 = 0
所以,98和63的最大公约数等于7。*/
//我们这里要用更相减损术的是指数,所以要让(p/q)^α1,(p/q)^α2,...,(p/q)^α(N-1),两两计算,互除,除到结果为1,即x1=x2,此时幂次为0,结果为1
如何求(p/q)^α1,(p/q)^α2,…,(p/q)^α(N-1)次幂αi的最大公约数
3.代码实现
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 110;
LL a[N], b[N], x[N];
int n;
LL gcd(LL a, LL b) //辗转相除法
{
return b ? gcd(b, a % b) : a;
}
LL gcd_sub(LL a, LL b) //辗转相减法(更相减损术)
{
if(a < b) swap(a, b); //与辗转相除法不同,只有当图中px大于py时才是px/py,即大的除小的
if(b == 1) return a;
return gcd_sub(b, a / b);
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%lld", &x[i]);
sort(x, x + n); //排序
int cnt = 0;
for(int i = 1; i < n; i ++)
{
if(x[i] != x[i - 1])
{
LL d = gcd(x[i], x[0]);
a[cnt] = x[i] / d; //求出分子p的αi次幂
b[cnt] = x[0] / d; //求出分母q的αi次幂
cnt ++;
}
}
LL up = a[0], down = b[0];
for(int i = 1; i < cnt; i ++) //因为要求公比pow(p / q, k)中k的最大值,
//即求次幂的最大值,所以求出每一项次幂的最大公约数即可
{
up = gcd_sub(up, a[i]);
down = gcd_sub(down, b[i]);
}
printf("%lld/%lld\n", up, down);
return 0;
}
%%%