【題解】ZeroJudge d366: 00294 – Divisors

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d366
【解題想法】質數表

  • sqrt(1e9) = 31622.8
  • 利用質數篩法找出小於sqrt(1e9)的所有質數。
  • 對每個 L <= n <= U 的 n 進行質因數分解。
    • n = b1^ p1 * b2 ^ p2 * b3^p3
    • 則 n 有 (1+p1) * (1+p2) * (1+p3) 個因數。
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int prime[32000];
vector <int> v;

int main() {
    for (int i = 2; i < 32000; i++){
        if (prime[i] == 0){
            v.push_back(i);
            for (int j = 2*i; j < 32000; j+=i){
                prime[j] = 1;
            }
        }
    }
    int T, L, U;
    cin >> T;
    while (T--){
        cin >> L >> U;
        int mx = 0, idx = 0;
        for (int i = L; i <= U; i++){
            int n = i, cnt = 1;
            for (auto b: v){
                int p = 0;
                while (n % b == 0){
                    p++;
                    n /= b;
                }
                cnt *= (p+1);
                if (n == 1) break;
            }
            if (cnt > mx){
                mx = cnt;
                idx = i;
            }
        }
        cout << "Between " << L << " and " << U << ", " << idx << " has a maximum of " << mx << " divisors.\n";
    }
    return 0;
}

分享本文 Share with friends