这个题用到了辗转相减法的一个特殊应用 简单分析一下如下
1223. 最大比例 X星球的某个大奖赛设了 M 级奖励。
每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。
比如：16,24,36,54，其等比值为：3/2。
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式 第一行为数字 N ，表示接下的一行包含 N 个正整数。
第二行 N 个正整数 Xi，用空格分开，每个整数表示调查到的某人的奖金数额。
输出格式 一个形如 A/B 的分数，要求 A、B 互质，表示可能的最大比例系数。
数据范围 0<N<100 0<Xi<1012 数据保证一定有解。
输入样例1： 3 1250 200 32 输出样例1： 25/4 输入样例2： 4 3125 32 32 200 输出样例2： 5/2 输入样例3： 3 549755813888 524288 2 输出样例3： 4/1
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N = 115; int n; ll sniper[N],p[N],q[N]; ll gcd(ll a, ll b) { if(!b) return a; else return gcd(b,a%b); } ll gcd_sub(ll a, ll b) { if(a < b) swap(a,b); if(b == 1) return a; else return gcd_sub(b,a/b); } int main() { int cnt = 0; cin >> n; for(int i = 0; i < n; i ++) scanf("%lld",&sniper[i]); sort(sniper,sniper+n); ll d; for(int i = 1; i < n; i ++) { if(sniper[i] == sniper[i - 1]) continue; d = gcd(sniper[i],sniper[0]); q[cnt] = sniper[i] / d; p[cnt] = sniper[0] / d; cnt ++; } ll res1 = q[0],res2 = p[0]; for(int i = 1; i < cnt; i ++) { res1 = gcd_sub(res1,q[i]); res2 = gcd_sub(res2,p[i]); } cout << res1 << '/' << res2 << endl; return 0; }