记录一下自己做题时产生的疑惑:
1.为什么求公比的最大约数等于所有分数的分子的最大约数/分母的最大约数?
因为分子分母互质,相当于分子分母是一一对应的。随便给出几个例子就行
2.将原数列转化为公比的数列?
将最小数视为q(此为公比)的0次方,其余各项比上第一项,求二者的最大公约数为了约分
3.怎么求比值最大公约数?
动态求最大公约数。初始项(原最小项)已经转化为1。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N= 110;
ll a[N],b[N],x[N];
ll gcd_sub(ll a,ll b)
{
if(a<b) swap(a,b);
if(b==1) return a;
ll d=gcd_sub(b,a/b);
return d;
}
ll gcd(ll a,ll b)
{
return (b==0)? a:gcd(b,a%b);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%lld",&x[i]);
sort(x,x+n);
// for(int i=0;i<n;i++) printf("%lld ",x[i]);
// puts("");
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;
b[cnt]=x[0]/d;
cnt++;
}
}
ll as=a[0],bs=b[0];
for(int i=0;i<cnt;i++)
{
as=gcd_sub(a[i],as);
bs=gcd_sub(b[i],bs);
}
printf("%d/%d",as,bs);
return 0;
}