最大公约数辗转相除法,真最简真分数定义

题目

给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。

样例

输入
7
3 5 7 9 11 13 15
输出
17

分析

最简真分数：分子比分母小，且两者的最大公约数为1
求最大公约数用辗转相除法：
让m>n r = m

while r>0:
r = m%n
m = n
n = r

return m
0 < a < b时，a%b = a

代码 #include<cstdio>#include<iostream>#include<vector>#include<algorithm>#include<string>#include<cctype>#include<cmath>using namespace std;const int maxx = 603;int arr[maxx];int gcd(int x1, int x2){ if (x1 < x2)swap(x1, x2); if (x1 == x2)return x1; int temp = x1; while (temp>0) { temp = x1 % x2; x1 = x2; x2 = temp; } return x1;}int main(){ int n; while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) scanf("%d", &arr[i]); int ans = 0; for(int i = 0;i<n;i++) for(int j = 0;j<n;j++) if (arr[i] < arr[j]) { int g = gcd(arr[i], arr[j]); if (g == 1)ans++; } printf("%dn", ans); }}