A46416. 最简真分数【辗转相除法】
填空题
中等
知识点
题目描述
最简真分数【辗转相除法】
题目描述
给出n个正整数，任取两个数分别作为分⼦和分母组成最简真分数，编程求共有⼏个这样的组合。
样例
输入
7
3 5 7 9 11 13 15
输出
17
参考答案
#include<iostream>
using namespace std;
int a[601];
int fun(int m,int n)//辗转相除求最大公约数
{
while(m%n!=0)
{
int r=m%n;
m=n;
n=r;
}
return n;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)//输入原始数据
{
cin>>a[i];
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)//循环枚举所有组合
{
if(fun(a[i],a[j])==1)//最大公约数为 1 证明是最简分数
{
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
上一题
下一题