test/ABC250-D.test.cpp

• View this file on GitHub
• Last update: 2023-03-04 23:54:34+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc250/submissions/39448263

Depends on

• linearSieve (線形篩・素因数分解/約数列挙) (src/math/linearSieve.hpp)
• binary-seach (整数二分探索) (src/template/binary-search.hpp)

Code

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

#include "../src/math/linearSieve.hpp"
#include "../src/template/binary-search.hpp"

#include <iostream>
#include <vector>
#include <functional>

int main() {
	// std::vector primes = zawa::linearSieve(1000000).enumPrime();
	// long long N; std::cin >> N;
	// std::size_t ans = 0;
	// for (std::size_t i = 0 ; i < primes.size() ; i++) {
	// 	auto f = [&](int p) -> bool {
	// 		long long v = 1LL;
	// 		for (int _ = 0 ; _ < 3 ; _++) {
	// 			if (v > N) {
	// 				return false;
	// 			}
	// 			v *= primes[p];
	// 		}
	// 		return v <= N / primes[i];
	// 	};
	// 	if (f(i) == false) {
	// 		break;
	// 	}
	// 	ans += zawa::binary_search((int)i, (int)primes.size() - 1, f) - i;
	// }
	// std::cout << ans << std::endl;
	
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 250 - D 250-like Number
 * https://atcoder.jp/contests/abc250/submissions/39448263
 */

#line 1 "test/ABC250-D.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/math/linearSieve.hpp"

#include <vector>
#include <utility>

namespace zawa {

class linearSieve {
private:
	std::vector<int> divs;
	std::vector<int> primes;

public:
	linearSieve() {}
	linearSieve(std::size_t n) : divs(n + 1, 1) {
		for (std::size_t i = 2 ; i < n + 1 ; i++) {
			if (divs[i] == 1) {
				divs[i] = i;
				primes.push_back((int)i);
			}
			for (const auto& p : primes) {
				if (p * i > n or p > divs[i]) {
					break;
				}
				divs[p * i] = p;
			}
		}
	}

	std::vector<std::pair<int, int>> factorize(int x) {
		std::vector res(0, std::pair(0, 0));
		while (x > 1) {
			res.emplace_back(divs[x], 0);
			while (divs[x] == res.back().first) {
				x /= divs[x];
				res.back().second++;
			}
		}
		return res;
	}

	std::vector<int> divisor(int x) {
		std::vector res(1, 1);
		for (const auto& [p, q] : factorize(x)) {
			std::size_t now = res.size();
			for (std::size_t i = 0 ; i < now ; i++) {
				int mul = p;
				for (int _ = 0 ; _ < q ; _++) {
					res.emplace_back(res[i] * mul);
					mul *= p;
				}
			}
		}
		return res;
	}

	std::vector<int> enumPrime() {
		return primes;
	}

	int numPrime() {
		return (int)primes.size();
	}

	bool isPrime(int x) {
		return (x != 0 and x != 1 and divs[x] == x);
	}

	int operator[](int x) {
		return divs[x];
	}
};

}
#line 2 "src/template/binary-search.hpp"

#include <cmath>

namespace zawa {

template <class T, class F>
T binary_search(T ok, T ng, const F& f) {
	while (std::abs(ok - ng) > 1) {
		T mid = ((ok + ng) >> 1);
		if (f(mid)) {
			ok = mid;
		}
		else {
			ng = mid;
		}
	}
	return ok;
}

}
#line 5 "test/ABC250-D.test.cpp"

#include <iostream>
#line 8 "test/ABC250-D.test.cpp"
#include <functional>

int main() {
	// std::vector primes = zawa::linearSieve(1000000).enumPrime();
	// long long N; std::cin >> N;
	// std::size_t ans = 0;
	// for (std::size_t i = 0 ; i < primes.size() ; i++) {
	// 	auto f = [&](int p) -> bool {
	// 		long long v = 1LL;
	// 		for (int _ = 0 ; _ < 3 ; _++) {
	// 			if (v > N) {
	// 				return false;
	// 			}
	// 			v *= primes[p];
	// 		}
	// 		return v <= N / primes[i];
	// 	};
	// 	if (f(i) == false) {
	// 		break;
	// 	}
	// 	ans += zawa::binary_search((int)i, (int)primes.size() - 1, f) - i;
	// }
	// std::cout << ans << std::endl;
	
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 250 - D 250-like Number
 * https://atcoder.jp/contests/abc250/submissions/39448263
 */

Back to top page