AcWing 1223. 最大比例
原题链接
中等
作者:
苦苣Java
,
2024-03-13 21:39:53
,
所有人可见
,
阅读 12
/*
M级奖励:
X0 X1 X2 X3 ....... X(m-1)
n个正整数
R0 R1 R2 ........ R(n-1)
公比 R1/R0 R2/R0 ....... R(n-1)/R0
相当于 (p/q)^s1 (p/q)^s2 ........ (p/q)^sn
设 p/q是最简形式: 1:gcd(p,q) == 1 2: p/q不能再表示成次幂形式
答案求 (p/q)^k 即k取最大
现在只需要求k最大即可 k满足的条件
例如 (p/q)^s1 = [(p/q)^k]^t = (p/q)^(k*t) 即 k是s1 s2 ... sn的最大公约数
即求 P^x 和 P^y的最大公约数 : (P^x,P^y) = [P^x,(P^y)/(P^x)]
用更相减损术 : 公约数 = (x,y) = (x,x-y)
*/
import java.util.*;
public class Main{
static int N = 110;
static long []w = new long[N];
static long []a = new long[N];//分子
static long []b = new long[N];//分母
static long gcd(long a,long b){
return b != 0 ? gcd(b,a%b) : a;
}
// 这个是辗转相减法的变式,用了原理而已,求出来的结果是幂的最大公约数。
static long gcd_sub(long a,long b){
if(b > a){
long t = b;
b = a;
a = t;
}
if(b == 1) return a;
return gcd_sub(b,a/b);
}
public static void main(String []args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for(int i = 0;i < n;i ++){
w[i] = in.nextLong();
}
Arrays.sort(w,0,n);
int cnt = 0;
for(int i = 1;i < n;i ++){
if(w[i] != w[i-1]){
long d = gcd(w[i],w[0]);
a[cnt] = w[i] / d; //分子 可以举个例子 (4,3) = 1。分子4/1 分母3/1
b[cnt] = w[0] / d; //分母
cnt ++;
}
}
long up = a[0],down = b[0];
for(int i = 1;i < cnt;i ++){
up = gcd_sub(up,a[i]);
down = gcd_sub(down,b[i]);
}
System.out.println(up+"/"+down);
}
}