[L,R]?范围内的所有可能的互质不同元素对。
在这里,我们将看到如何计算范围内的互质对的数量,在此范围内,数量不会超过一对。
在讨论逻辑之前,让我们看看什么是互质数?互素数是那些只有一个正整数除数(即1)的数。换句话说,我们可以说这两个数的GCD为1。
在这里,我们提供了下限和上限。如果下限和上限分别为1和6,则有三对。它们是(1、2),(3、4)和(5、6)
解决这个问题的方法是这样的:如果数字是连续的,则它们总是互质的。因此计数将为(R–L+1)/2。如果(R–L+1)为奇数,则将剩下一个数字,该数字将不会成对出现,如果为偶数,则所有数字将成对出现
算法
countCoPrimePairs(L,R)
Begin return (R – L + 1)/2 End
示例
#include <iostream> using namespace std; int countCoPrimePairs(int L, int R) { return (R - L + 1)/2; } main() { int l = 1, r = 6; cout << "Number of co-prime pairs: " << countCoPrimePairs(l, r); }
输出结果
Number of co-prime pairs: 3