数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中计算1到N之间无序互质数对个数的查询
在这个问题中，我们得到了Q个查询，每个查询包含一个数字N。我们的任务是创建一个程序来解决C++中计算1到N之间无序互质数对个数的查询。
互质数，也称为互素数或相对素数，是指只有一公因数1的一对数。
让我们来看一个例子来理解这个问题：
输入：Q = 2，查询 = [5, 6]
输出: 10
解释
数对为：(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)
解决方案
解决这个问题最有效的方案是使用欧拉函数φ(N)。φ(N)计算给定值N之前的互质数总数。欧拉函数是：
$$𝛷(𝑁) = 𝑁 ∏_{p|N} (1 − \frac{1}{p}),$$
其中p是N的所有质因数。
现在，我们将预先计算直到N的无序互质数对个数的值。然后从预先计算的数组中查找每个查询的值。
示例
#include <iostream>
using namespace std;
#define N 10001
int phi[N];
int CoPrimePairs[N];
void computePhi(){
for (int i = 1; i < N; i++)
phi[i] = i;
for (int p = 2; p < N; p++) {
if (phi[p] == p) {
phi[p] = p - 1;
for (int i = 2 * p; i < N; i += p) {
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
void findCoPrimes() {
computePhi();
for (int i = 1; i < N; i++)
CoPrimePairs[i] = CoPrimePairs[i - 1] + phi[i];
}
int main() {
findCoPrimes();
int Q = 3;
int query[] = { 5, 7, 9};
for (int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": Number of prime pairs is "<<CoPrimePairs[query[i]]<<endl;
return 0;
}输出
For Query 1: Number of prime pairs is 10 For Query 2: Number of prime pairs is 18 For Query 3: Number of prime pairs is 28
更新于：2020年10月9日
201 次浏览
广告