test/Math/enumerate_divisor/aoj-ITP1_3_D.test2.cpp

View this file on GitHub
Last update: 2025-03-16 00:49:34+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_D

Depends on

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_D

#include "Math/enumerate_divisor.hpp"
#include "Math/prime_factorize.hpp"
#include <bits/stdc++.h>

using namespace std;

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

    vector<pair<long long, long long>> prime_factors = prime_factorize(c);

    vector<long long> divisor = enumerate_divisor(prime_factors);

    long long ans = 0;

    for (long long n : divisor)
    {
        if (a <= n && n <= b)
        {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

#line 1 "test/Math/enumerate_divisor/aoj-ITP1_3_D.test2.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_D

#line 1 "Math/enumerate_divisor.hpp"
#include <bits/stdc++.h>
using namespace std;

vector<long long> enumerate_divisor(long long n)
{
    assert(0 < n);
    vector<long long> dst;
    for (long long i = 1; i * i <= n; i++)
    {
        if (n % i != 0)
            continue;
        dst.push_back(i);
        if (i * i != n)
            dst.push_back(n / i);
    }
    sort(dst.begin(), dst.end());
    return dst;
}

vector<long long> enumerate_divisor(const vector<pair<long long, long long>> &prime_factors)
{
    assert(all_of(prime_factors.begin(), prime_factors.end(), [](const auto &n)
                  { return 0 < n.first && 0 < n.second; }));

    vector<long long> dst;
    auto dfs = [&](int now, long long n, auto dfs) -> void
    {
        if (now == prime_factors.size())
        {
            dst.push_back(n);
            return;
        }

        auto [p, c] = prime_factors[now];
        for (int i = 0; i < c + 1; i++)
        {
            dfs(now + 1, n, dfs);
            if (i != c)
            {
                n *= p;
            }
        }
    };

    dfs(0, 1, dfs);

    sort(dst.begin(), dst.end());

    return dst;
}
#line 2 "Math/prime_factorize.hpp"
using namespace std;

vector<pair<long long, long long>> prime_factorize(long long N)
{
    assert(0 < N);

    long long tempN = N;
    vector<pair<long long, long long>> dst;
    for (long long i = 2; i * i <= tempN; i++)
    {
        if (N % i == 0)
        {
            dst.push_back(make_pair(i, 0));
            while (N % i == 0)
            {
                dst.back().second++;
                N /= i;
            }
        }
    }
    if (N != 1)
        dst.push_back(make_pair(N, 1));
    return dst;
}
#line 6 "test/Math/enumerate_divisor/aoj-ITP1_3_D.test2.cpp"

using namespace std;

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

    vector<pair<long long, long long>> prime_factors = prime_factorize(c);

    vector<long long> divisor = enumerate_divisor(prime_factors);

    long long ans = 0;

    for (long long n : divisor)
    {
        if (a <= n && n <= b)
        {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	3 MB
g++	01_corner_00.in	AC	4 ms	3 MB
g++	01_corner_01.in	AC	4 ms	3 MB
g++	01_corner_02.in	AC	4 ms	3 MB
g++	01_corner_03.in	AC	5 ms	3 MB
g++	01_corner_04.in	AC	4 ms	3 MB
g++	01_corner_05.in	AC	4 ms	3 MB
g++	01_corner_06.in	AC	4 ms	3 MB
g++	02_rand_00.in	AC	4 ms	3 MB
g++	02_rand_01.in	AC	4 ms	3 MB
g++	02_rand_02.in	AC	4 ms	3 MB
g++	02_rand_03.in	AC	4 ms	3 MB
g++	02_rand_04.in	AC	4 ms	3 MB
g++	02_rand_05.in	AC	4 ms	3 MB
g++	02_rand_06.in	AC	4 ms	3 MB
g++	02_rand_07.in	AC	4 ms	3 MB
g++	03_maximum_00.in	AC	4 ms	3 MB
g++	03_maximum_01.in	AC	4 ms	3 MB
g++	03_maximum_02.in	AC	4 ms	3 MB
g++	03_maximum_03.in	AC	4 ms	3 MB