test/mobiusFunction.test.cpp

• View this file on GitHub
• Last update: 2023-03-05 22:25:53+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A

Depends on

• mobiusFunction (メビウス関数値の列挙) (src/math/mobiusFunction.hpp)
• primeSieve (エラトステネスの篩） (src/math/primeSieve.hpp)

Code

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

#include "../src/math/mobiusFunction.hpp"

#include <iostream>
#include <cassert>

int main() {
	zawa::mobiusFunction mf(10);
	std::vector ans = { 1, -1, -1, 0, -1, 1, -1, 0, 0, 1 };
	for (int i = 0 ; i < 10 ; i++) {
		assert(ans[i] == mf[i + 1]);
	}
	std::cout << "Hello World" << std::endl;
}

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

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

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

#include <vector>

namespace zawa {

class primeSieve {
private:
	std::vector<bool> sieve;

public:
	primeSieve() {}
	primeSieve(std::size_t n) : sieve(n + 1, true) {
		if (n >= 0) {
			sieve[0] = false;
		}
		if (n >= 1) {
			sieve[1] = false;
		}
		for (std::size_t i = 2 ; i <= n ; i++) {
			if (sieve[i]) {
				for (std::size_t j = i * 2 ; j <= n ; j += i) {
					sieve[j] = false;
				}
			}
		}
	}

	inline bool operator[](std::size_t i) const {
		return sieve[i];
	}

	inline std::size_t size() const {
		return sieve.size();
	}
};

}// namespace zawa
#line 4 "src/math/mobiusFunction.hpp"

#line 6 "src/math/mobiusFunction.hpp"

namespace zawa {

class mobiusFunction {
private:
	std::vector<int> table;

public:
	mobiusFunction() {}
	mobiusFunction(std::size_t n) : table(std::vector(n + 1, 1)) {
		primeSieve siv(n);
		for (std::size_t i = 2 ; i <= n ; i++) {
			if (siv[i]) {
				for (std::size_t j = i ; j <= n ; j += i) {
					if (!(j % (i * i))) {
						table[j] = 0;
					}
					else {
						table[j] *= -1;
					}
				}
			}
		}
	}

	inline int operator[](int i) const {
		return table[i];
	}
};

}// namespace zawa
#line 4 "test/mobiusFunction.test.cpp"

#include <iostream>
#include <cassert>

int main() {
	zawa::mobiusFunction mf(10);
	std::vector ans = { 1, -1, -1, 0, -1, 1, -1, 0, 0, 1 };
	for (int i = 0 ; i < 10 ; i++) {
		assert(ans[i] == mf[i + 1]);
	}
	std::cout << "Hello World" << std::endl;
}

Back to top page