カーマイケル関数 (Carmichael function) の数表
(include/emthrm/math/carmichael_function_init.hpp)
カーマイケル関数 (Carmichael function)
$n \in \mathbb{N}^+$ に対して
\[\forall a \in \mathbb{N}^+,\ a \perp n \implies a^x \equiv 1 \pmod{n}\]
を満たす最小の $x \in \mathbb{N}^+$ を $\lambda(n)$ と定義する。
素因数分解 $n = \prod_{i = 1}^k p_i^{e_i}$ に対して
\[\lambda(n) =
\begin{cases}
1 & (n = 1, 2), \\
2 & (n = 4), \\
2^{e - 2} & (\exists e \geq 3,\ n = 2^e), \\
(p - 1)p^{e - 1} & (\exists p \text{ : 奇素数},\ \exists e \in \mathbb{N}^+,\ n = p^e), \\
\mathrm{lcm} (\lambda(p_1^{e_1}),\ldots, \lambda(p_k^{e_k})) & (\text{otherwise})
\end{cases}\]
が成り立つ。
仕様
名前
戻り値
long long carmichael_function(long long n);
カーマイケル関数 $\lambda(n)$
数表
名前
戻り値
std::vector<long long> carmichael_function_init(const long long low, const long long high);
カーマイケル関数 $\lambda(n)$ ($\mathrm{low} \leq n \leq \mathrm{high}$) の数表
参考文献
Robert D. Carmichael: Note on a new number theory function, Bulletin of the American Mathematical Society , Vol. 16, pp. 232–238 (1910). https://doi.org/10.1090/S0002-9904-1910-01892-9
http://integers.hatenablog.com/entry/2017/06/08/191649
https://en.wikipedia.org/wiki/Carmichael_function
https://github.com/spaghetti-source/algorithm/blob/8af3698b8a7583035857280ab324c8ae75c70374/number_theory/carmichael_lambda.cc
TODO
https://onlinejudge.u-aizu.ac.jp/problems/2720
Depends on
Code
#ifndef EMTHRM_MATH_CARMICHAEL_FUNCTION_INIT_HPP_
#define EMTHRM_MATH_CARMICHAEL_FUNCTION_INIT_HPP_
#include <numeric>
#include <vector>
#include "emthrm/math/prime_sieve.hpp"
namespace emthrm {
std :: vector < long long > carmichael_function_init ( const long long low ,
const long long high ) {
std :: vector < long long > lambda ( high - low , 1 ), tmp ( high - low );
std :: iota ( tmp . begin (), tmp . end (), low );
if ( low == 0 && high > 0 ) lambda [ 0 ] = 0 ;
for ( long long i = ( low + 7 ) / 8 * 8 ; i < high ; i += 8 ) {
tmp [ i - low ] >>= 1 ;
}
long long root = 1 ;
while (( root + 1 ) * ( root + 1 ) < high ) ++ root ;
for ( const int p : prime_sieve < true > ( root )) {
for ( long long i = ( low + p - 1 ) / p * p ; i < high ; i += p ) {
if ( i == 0 ) continue ;
tmp [ i - low ] /= p ;
long long phi = p - 1 ;
for (; tmp [ i - low ] % p == 0 ; tmp [ i - low ] /= p ) {
phi *= p ;
}
lambda [ i - low ] = std :: lcm ( lambda [ i - low ], phi );
}
}
for ( int i = 0 ; i < high - low ; ++ i ) {
if ( tmp [ i ] > 1 ) lambda [ i ] = std :: lcm ( lambda [ i ], tmp [ i ] - 1 );
}
return lambda ;
}
} // namespace emthrm
#endif // EMTHRM_MATH_CARMICHAEL_FUNCTION_INIT_HPP_
#line 1 "include/emthrm/math/carmichael_function_init.hpp"
#include <numeric>
#include <vector>
#line 1 "include/emthrm/math/prime_sieve.hpp"
#line 6 "include/emthrm/math/prime_sieve.hpp"
namespace emthrm {
template < bool GETS_ONLY_PRIME >
std :: vector < int > prime_sieve ( const int n ) {
std :: vector < int > smallest_prime_factor ( n + 1 ), prime ;
std :: iota ( smallest_prime_factor . begin (), smallest_prime_factor . end (), 0 );
for ( int i = 2 ; i <= n ; ++ i ) {
if ( smallest_prime_factor [ i ] == i ) [[ unlikely ]] prime . emplace_back ( i );
for ( const int p : prime ) {
if ( i * p > n || p > smallest_prime_factor [ i ]) break ;
smallest_prime_factor [ i * p ] = p ;
}
}
return GETS_ONLY_PRIME ? prime : smallest_prime_factor ;
}
} // namespace emthrm
#line 8 "include/emthrm/math/carmichael_function_init.hpp"
namespace emthrm {
std :: vector < long long > carmichael_function_init ( const long long low ,
const long long high ) {
std :: vector < long long > lambda ( high - low , 1 ), tmp ( high - low );
std :: iota ( tmp . begin (), tmp . end (), low );
if ( low == 0 && high > 0 ) lambda [ 0 ] = 0 ;
for ( long long i = ( low + 7 ) / 8 * 8 ; i < high ; i += 8 ) {
tmp [ i - low ] >>= 1 ;
}
long long root = 1 ;
while (( root + 1 ) * ( root + 1 ) < high ) ++ root ;
for ( const int p : prime_sieve < true > ( root )) {
for ( long long i = ( low + p - 1 ) / p * p ; i < high ; i += p ) {
if ( i == 0 ) continue ;
tmp [ i - low ] /= p ;
long long phi = p - 1 ;
for (; tmp [ i - low ] % p == 0 ; tmp [ i - low ] /= p ) {
phi *= p ;
}
lambda [ i - low ] = std :: lcm ( lambda [ i - low ], phi );
}
}
for ( int i = 0 ; i < high - low ; ++ i ) {
if ( tmp [ i ] > 1 ) lambda [ i ] = std :: lcm ( lambda [ i ], tmp [ i ] - 1 );
}
return lambda ;
}
} // namespace emthrm
Back to top page