verify/aoj-ITP1_3_D-divisors.test.cpp

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/3/ITP1_3_D

Depends on

algorithm/Math/NumberTheory/divisors.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/3/ITP1_3_D"

#include <algorithm>
#include <iostream>

#include "../algorithm/Math/NumberTheory/divisors.hpp"

int main() {
    int a, b, c;
    std::cin >> a >> b >> c;

    const auto &&divs = algorithm::divisors(c);
    auto left = std::lower_bound(divs.cbegin(), divs.cend(), a);
    auto right = std::upper_bound(divs.cbegin(), divs.cend(), b);

    auto ans = right - left;
    std::cout << ans << std::endl;
}

#line 1 "verify/aoj-ITP1_3_D-divisors.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/3/ITP1_3_D"

#include <algorithm>
#include <iostream>

#line 1 "algorithm/Math/NumberTheory/divisors.hpp"



#line 5 "algorithm/Math/NumberTheory/divisors.hpp"
#include <cassert>
#include <map>
#include <vector>

namespace algorithm {

// 約数列挙．O(√N).
template <typename Type>
std::vector<Type> divisors(Type n) {
    assert(n >= 1);
    std::vector<Type> res;  // res[]:=(自然数nの約数の集合).
    for(Type p = 1; p * p <= n; ++p) {
        if(n % p == 0) {
            res.push_back(p);
            Type q = n / p;
            if(q != p) res.push_back(q);
        }
    }
    std::sort(res.begin(), res.end());
    return res;
}

// 高速約数列挙．
template <typename Type>
std::vector<Type> divisors(const std::map<Type, int> &pf) {
    std::vector<Type> res({1});
    for(const auto &[p, cnt] : pf) {
        const int sz = res.size();
        Type b = 1;
        for(int i = 0; i < cnt; ++i) {
            b *= p;
            for(int j = 0; j < sz; ++j) res.push_back(res[j] * b);
        }
    }
    std::sort(res.begin(), res.end());
    return res;
}

}  // namespace algorithm


#line 7 "verify/aoj-ITP1_3_D-divisors.test.cpp"

int main() {
    int a, b, c;
    std::cin >> a >> b >> c;

    const auto &&divs = algorithm::divisors(c);
    auto left = std::lower_bound(divs.cbegin(), divs.cend(), a);
    auto right = std::upper_bound(divs.cbegin(), divs.cend(), b);

    auto ans = right - left;
    std::cout << ans << std::endl;
}