在写题目之前,首先来明确一个概念
$\color{red}{辗转相除法}$ (gcd)
作用:用来求解a,b的最大公约数
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
$\color{red}{辗转相减法}$ (sub_gcd)
作用:用来求解 $x^a$,$x^b$中以x为底,a,b的最大公约数为指数的结果
也就是$x^{gcd(a,b)}$
LL sub_gcd(LL a,LL b)
{
if(a<b) return sub_gcd(b,a);
if(b==1) return a;
return sub_gcd(b,a/b);
}
好了,剩下的便简单了
这里因为是求解分数,所以采用存储w[1]~w[n-1]中所有数与w[0]的比值的方法
$\color{blue}{排序后w[0]为最小值,保证后续都可以化简为x^a的形式}$
想要求解最终的答案,便是求解结果中x的所有指数的最大公约数
$\color{blue}{形式为x^{gcd(指数)}}$
所以就要用到辗转相减法。。。
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=110;
int n;
LL w[N];
LL a[N],b[N];
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
LL sub_gcd(LL a,LL b)
{
if(a<b) return sub_gcd(b,a);
if(b==1) return a;
return sub_gcd(b,a/b);
}
int main()
{
cin >> n;
for(int i=0;i<n;i++) cin >> w[i];
sort(w,w+n);
int cnt=0;
for(int i=1;i<n;i++)
if(w[i]!=w[i-1])//记得去重
{
LL d=gcd(w[i],w[0]);
a[cnt]=w[i]/d;
b[cnt++]=w[0]/d;
}
LL x=a[0],y=b[0];
for(int i=1;i<cnt;i++)
{
x=sub_gcd(x,a[i]);
y=sub_gcd(y,b[i]);
}
cout << x << '/' << y;
return 0;
}
第一次写题解,如有不足之处还请指出
就酱 bye~