test/yukicoder/yuki_888_1.test.cpp

View this file on GitHub
Last update: 2024-10-21 04:45:56+09:00
Problem: https://yukicoder.me/problems/no/888

Depends on

素数判定、約数列挙 (lib/math/prime.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/888"
#include <bits/stdc++.h>
using namespace std;

#include "../../lib/math/prime.hpp"

int main(){
    long long n; cin >> n;
    long long ans = 0;
    for(auto x : prime::divisor(n)){
        ans += x;
    }
    cout << ans << "\n";
}

#line 1 "test/yukicoder/yuki_888_1.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/888"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/math/prime.hpp"

/**
 * @brief 素数判定、約数列挙
 * @docs docs/math/prime.md
 */

namespace prime{

    template <typename T>
    bool isPrime(T n){
        switch(n) {
        case 0: // fall-through
        case 1: return false;
        case 2: return true;
        }

        if(n % 2 == 0) return false;

        for(T i = 3; i * i <= n; i += 2){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }

    template <typename T>
    vector<pair<T, T>> factorize(T n) {
        vector<pair<T, T>> ret;
        for(T i = 2; i * i <= n; i++) {
            if(n % i != 0) continue;
            T tmp = 0;
            while(n % i == 0) {
                tmp++;
                n /= i;
            }
            ret.push_back(make_pair(i, tmp));
        }
        if(n != 1) ret.push_back(make_pair(n, 1));
        return ret;
    }

    template <typename T>
    vector<T> divisor(T n){
        T rt = sqrt(n);
        vector<T> res, resB;
        for(T i = 1; i * i <= n; i++){
            if(n % i == 0){
                res.push_back(i);
                T j = n / i;
                if(j != rt){
                    resB.push_back(j);
                }
            }
        }
        for(int i = (int) resB.size() - 1; i >= 0; i--){
            res.push_back(resB[i]);
        }
        return res;
    }
}
#line 6 "test/yukicoder/yuki_888_1.test.cpp"

int main(){
    long long n; cin >> n;
    long long ans = 0;
    for(auto x : prime::divisor(n)){
        ans += x;
    }
    cout << ans << "\n";
}