网站手机客户端如何开发,中国工程网查询,邯郸信息港手机版,设计师常用的设计论坛题目描述
“蓝桥杯”练习系统 (lanqiao.cn) 题目分析
思路#xff1a;
1.去重排序将其进行预处理
2.用gcd得到最简比值
3.用gcd_sub分别计算分子、分母的指数最大公约数 #includebits/stdc.h
using namespace std;
const int N 110;
typedef long long ll;
ll…题目描述
“蓝桥杯”练习系统 (lanqiao.cn) 题目分析
思路
1.去重排序将其进行预处理
2.用gcd得到最简比值
3.用gcd_sub分别计算分子、分母的指数最大公约数 #includebits/stdc.h
using namespace std;
const int N 110;
typedef long long ll;
ll n, cnt, a[N], x[N], y[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);if(b 1)return a;return gcd_sub(b, a / b);
}
int main()
{cin n;for(int i 1; i n; i ){cin a[i];}sort(a 1, a 1 n);for(int i 2; i n; i ){if(a[i] ! a[i - 1]){ll d gcd(a[i], a[1]);cnt ; x[cnt] a[i] / d;//分子 y[cnt] a[1] / d;//分母 }}ll u x[1], d y[1];for(int i 2; i cnt; i ){u gcd_sub(u, x[i]);d gcd_sub(d, y[i]);}cout u / d;return 0;
}
