資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中計算範圍內公約數為素數因子冪的1的數字
給定兩個數字start和end，代表一個正整數範圍。目標是查詢位於範圍[start,end]內，並且其素因子分解中所有素因子的冪的公約數都等於1的數字個數。
如果一個數字的素因子分解為2p * 3q * 5r……，那麼冪p、q、r……的公約數應為1。
讓我們透過例子來理解。
例如
輸入 - start = 1, end = 10
輸出 - 範圍內公約數為素數因子冪的1的數字個數為：6
解釋 - 這些數字是
2 (21), 3 (31), 5 (51), 7 (71), 8 (23) 和 10 (21*51)。每個素因子分解的冪的公約數都為1。
輸入 - start = 11, end = 20
輸出 - 範圍內公約數為素數因子冪的1的數字個數為：9
解釋 - 這些數字是
11 (111), 12 (31*22), 13 (131), 14 (21*71), 15 (31*51), 17 (171), 18 (21*32), 19 (191) 和 20 (22*51)。每個素因子分解的冪的公約數都為1。
下面程式中使用的演算法如下
在這個方法中，我們將計算從start到end範圍內不是完全冪的數字個數。因為非完全冪將滿足上述條件。為此，我們將找到所有完全冪，並將它們從總數中減去。
答案將是 = start-end +1 - (範圍[start,end]內是完全冪的數字個數)。
- 將範圍變數start和end作為輸入。
- 使用向量vec儲存大於3的冪。
- 使用集合sett儲存完全平方數。
- 使用集合sett_2儲存不是完全平方數的數字。
- 函式calculate()填充向量vec和集合sett和sett_2。用於分離完全平方數、非完全平方數和冪>3的數字。
- 使用for迴圈從i=2遍歷到i<size。
- 將完全冪i*i插入sett。
- 如果sett.find(i) != sett.end())返回true，則i是完全平方數，存在於sett中，因此無需執行任何操作。
- 執行while迴圈，直到當前數字的冪小於large。
- 將奇數冪插入sett_2，因為偶數冪是完全平方數，存在於sett中。
- 最後，使用for迴圈將sett_2的排序值插入向量vec。
- 函式GCD_1(long int start, long int end)以範圍作為輸入，並返回範圍內公約數為素數因子冪的1的數字個數。
- 呼叫calculate()。
- 計算範圍內的完全平方數為per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1))。
- 使用upper_bound(vec.begin(), vec.end(), end) - vec.begin()計算vec中start的上界值。
- 類似地，使用bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin()計算vec中end的下界值。
- 計算完全冪為per_pow = per_sq + (top - bottom)。
- 答案將是count = (end - start + 1) - per_pow。
- 最後返回count作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
#define size 1000005
#define large 1e18
vector < long int > vec;
set < long int > sett;
set < long int > sett_2;
void calculate() {
for (long int i = 2; i < size; i++) {
sett.insert(i * i);
if (sett.find(i) != sett.end()) {
continue;
}
long int total = i;
while (i * i <= large / total) {
total *= (i * i);
sett_2.insert(total);
}
}
for (auto it: sett_2) {
vec.push_back(it);
}
}
long int GCD_1(long int start, long int end) {
calculate();
long int per_sq = floor(sqrtl(end)) - floor(sqrtl(start - 1));
long int top = upper_bound(vec.begin(), vec.end(), end) - vec.begin();
long int bottom = lower_bound(vec.begin(), vec.end(), start) - vec.begin();
long int per_pow = per_sq + (top - bottom);
long int count = (end - start + 1) - per_pow;
return count;
}
int main() {
long int start = 10, end = 40;
cout << "Count of numbers in a range having GCD of powers of prime factors equal to 1 are: " << GCD_1(start, end);
return 0;
}如果我們執行上述程式碼，它將生成以下輸出：
輸出
Count of numbers in a range having GCD of powers of prime factors equal to 1 are: 7
更新於：2021年1月29日
78 次瀏覽
廣告