mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

オイラーのφ関数（オイラーのトーシェント関数）テーブル
(math/euler_phi_table.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "math/euler_phi_table.hpp"

オイラーのφ関数（オイラーのトーシェント関数）テーブル

使い方

• vector<int> euler_phi_table(int n) : $\phi(x)$ ($1 \leq x \leq n$) が配列の添え字 $1, 2, \cdots ,n$ に格納された長さ $n+1$ の配列を返す $O(N \log N \log N)$

概要

$\phi(n)$ : $1$ から $n$ までの自然数のうち、 $n$ と互いに素なものの個数

$\phi(n) = \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

これを、素因数側から求めることによって、$\phi(x)$ ($1 \leq x \leq n$) についてまとめて計算することが可能となる。

Verified with

• verify/aoj/id/2286.test.cpp

Code

#pragma once

#include<vector>

std::vector<int> euler_phi_table(int n){
	std::vector<int> phi(n + 1);
	for(int i = 0;i <= n;i++){
		phi[i] = i;
	}
	for(int i = 2;i <= n;i++){
		if(phi[i] == i){
			for(int j = i;j <= n;j += i){
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
	return phi;
}

#line 2 "math/euler_phi_table.hpp"

#include<vector>

std::vector<int> euler_phi_table(int n){
	std::vector<int> phi(n + 1);
	for(int i = 0;i <= n;i++){
		phi[i] = i;
	}
	for(int i = 2;i <= n;i++){
		if(phi[i] == i){
			for(int j = i;j <= n;j += i){
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
	return phi;
}

Back to top page