mobiusFunction (メビウス関数値の列挙)
(src/math/mobiusFunction.hpp)

• View this file on GitHub
• Last update: 2023-03-05 22:25:53+09:00
• Include: #include "src/math/mobiusFunction.hpp"

概要

正整数 $n$ 以下の正整数についてメビウス関数値 $\mu$ を列挙する

メビウス関数とは以下に定義される関数(参考: wikipedia）

• 平方数で割り切れるなら0
• 偶数個の素因数の積で表現されるなら1
• 奇数個の素因数の積で表現されるなら-1

機能

コンストラクタ

(1) zawa::mobiusFunction()
(2) zawa::mobiusFunction(std::size_t n)

(1)

デフォルトコンストラクタ

(2)

$n$ 以下のメビウス関数値を列挙する

計算量

$O(n\log (\log n))$

operator

[]

inline int operator[](std::size_t i) const

$\mu(i)$ を返す

制約

$1\ \le\ i\ \le\ n$

計算量

$O(1)$

Depends on

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

Verified with

• test/mobiusFunction.test.cpp

Code

#pragma once

#include "./primeSieve.hpp"

#include <vector>

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 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

Back to top page