資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告