【題解】CSES 1713 Counting Divisors

【題目敘述】https://cses.fi/problemset/task/1713/

#include <iostream>
#include <vector>
using namespace std;
 
int n, x, p[1000005];
 
int main() {
    cin >> n;
    for (int i = 2; i < 1000005; i++){
        if (!p[i]){
            for (int j = i; j < 1000005; j += i){
                p[j] = i;
            }
        }
    }
    while (n--){
        cin >> x;
        vector <pair<int, int> > v;
        int ans = 1;
        while (p[x]){
            if (!v.empty() && p[x] == v.back().first) v.back().second++;
            else v.push_back({p[x], 2});
            x /= p[x];
        }
        for (auto i:v){
            ans *= i.second;
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends