d366 - 00294 - Divisors
題目描述
題目要求找出給定範圍 [a, b] 內，擁有最多除數的數字。如果有多個數字擁有相同的最大除數數量，則輸出最小的那個數字。
解題思路
程式碼透過迴圈迭代範圍 [a, b] 中的每個數字，並計算每個數字的除數數量。除數數量計算基於質因數分解。對於每個數字 j，程式碼嘗試找到其所有質因數，並計算每個質因數的冪次。除數的總數由質因數冪次的加一的乘積計算得出。程式碼追蹤目前找到的最大除數數量和對應的數字，並在迴圈結束時輸出結果。
複雜度分析
- 時間複雜度: O(N * sqrt(B))，其中 N 是測試案例的數量，B 是範圍的最大值。對於每個數字，質因數分解的時間複雜度為 O(sqrt(j))，最壞情況下 j 等於 B。
- 空間複雜度: O(1)，程式碼只使用固定數量的變數，不依賴於輸入大小。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
long long a,b,n;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;++i){
cin >> a >> b;
long long ans,ma=0;
for(long long j=a;j<=b;++j){
long long tmp=j,ba=2,bat=1,trs=1;
while(tmp!=1&&ba<=sqrt(tmp)){
while(tmp%ba==0){
tmp/=ba;
++bat;
}
trs*=bat;
bat=1;
++ba;
}
if(tmp!=1){
trs*=2;
}
if(trs>ma){
ans=j;
ma=trs;
}
}
cout << "Between " << a << " and " << b << ", " << ans << " has a maximum of " << ma << " divisors.\n";
}
}