test/math/sieve_of_eratosthenes/aoj_itp1_3_d.test.cpp

• View this file on GitHub
• Last update: 2024-10-12 16:54:24+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/3/ITP1_3_D

Depends on

• エラトステネスの篩 (src/math/sieve_of_eratosthenes.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/3/ITP1_3_D

#include "src/math/sieve_of_eratosthenes.hpp"

#include <iostream>

using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int res = 0;
	for (auto d : SieveOfEratosthenes(c).divisor(c)) {
		if (a <= d && d <= b) ++res;
	}
	cout << res << endl;

	return 0;
}

#line 1 "test/math/sieve_of_eratosthenes/aoj_itp1_3_d.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/3/ITP1_3_D

#line 1 "src/math/sieve_of_eratosthenes.hpp"



#include <numeric>
#include <utility>
#include <vector>

class SieveOfEratosthenes {
private:
	std::vector<int> min_factor;

public:
	SieveOfEratosthenes(int n) : min_factor(n + 1) {
		std::iota(min_factor.begin(), min_factor.end(), 0);
		for (int p = 2; p * p <= n; ++p) {
			if (min_factor[p] < p) continue;
			for (int q = p * p; q <= n; q += p) {
				if (min_factor[q] == q) min_factor[q] = p;
			}
		}
	}

	bool is_prime(int n) { return n > 1 && min_factor[n] == n; }

	std::vector<std::pair<int, int>> factorize(int n) {
		std::vector<std::pair<int, int>> res;
		while (n > 1) {
			int p = min_factor[n];
			int exp = 0;
			while (min_factor[n] == p) {
				n /= p;
				++exp;
			}
			res.emplace_back(p, exp);
		}
		return res;
	}

	std::vector<int> divisor(int n) {
		std::vector<int> res{1};
		for (auto const &[p, exp] : factorize(n)) {
			int sz = res.size();
			for (int i = 0; i < sz; ++i) {
				int x = 1;
				for (int j = 0; j < exp; ++j) {
					x *= p;
					res.push_back(res[i] * x);
				}
			}
		}
		return res;
	}
};


#line 4 "test/math/sieve_of_eratosthenes/aoj_itp1_3_d.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int res = 0;
	for (auto d : SieveOfEratosthenes(c).divisor(c)) {
		if (a <= d && d <= b) ++res;
	}
	cout << res << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	13 ms	7 MB
g++	01_corner_00.in	AC	12 ms	7 MB
g++	01_corner_01.in	AC	12 ms	7 MB
g++	01_corner_02.in	AC	12 ms	7 MB
g++	01_corner_03.in	AC	12 ms	7 MB
g++	01_corner_04.in	AC	12 ms	7 MB
g++	01_corner_05.in	AC	13 ms	7 MB
g++	01_corner_06.in	AC	12 ms	7 MB
g++	02_rand_00.in	AC	12 ms	7 MB
g++	02_rand_01.in	AC	12 ms	7 MB
g++	02_rand_02.in	AC	12 ms	7 MB
g++	02_rand_03.in	AC	13 ms	7 MB
g++	02_rand_04.in	AC	12 ms	7 MB
g++	02_rand_05.in	AC	12 ms	7 MB
g++	02_rand_06.in	AC	13 ms	7 MB
g++	02_rand_07.in	AC	12 ms	7 MB
g++	03_maximum_00.in	AC	12 ms	7 MB
g++	03_maximum_01.in	AC	13 ms	7 MB
g++	03_maximum_02.in	AC	12 ms	7 MB
g++	03_maximum_03.in	AC	12 ms	7 MB
clang++	00_sample_00.in	AC	12 ms	11 MB
clang++	01_corner_00.in	AC	11 ms	13 MB
clang++	01_corner_01.in	AC	13 ms	15 MB
clang++	01_corner_02.in	AC	12 ms	13 MB
clang++	01_corner_03.in	AC	11 ms	7 MB
clang++	01_corner_04.in	AC	11 ms	13 MB
clang++	01_corner_05.in	AC	11 ms	11 MB
clang++	01_corner_06.in	AC	12 ms	9 MB
clang++	02_rand_00.in	AC	11 ms	15 MB
clang++	02_rand_01.in	AC	11 ms	13 MB
clang++	02_rand_02.in	AC	12 ms	13 MB
clang++	02_rand_03.in	AC	11 ms	11 MB
clang++	02_rand_04.in	AC	11 ms	11 MB
clang++	02_rand_05.in	AC	12 ms	13 MB
clang++	02_rand_06.in	AC	11 ms	11 MB
clang++	02_rand_07.in	AC	12 ms	7 MB
clang++	03_maximum_00.in	AC	12 ms	9 MB
clang++	03_maximum_01.in	AC	12 ms	13 MB
clang++	03_maximum_02.in	AC	12 ms	11 MB
clang++	03_maximum_03.in	AC	12 ms	11 MB

Back to top page