CPLib.ZP
Defined in cp-library@0.16.0
素数pを法とする整数の環の型ZP pを与えるモジュール。
法pは静的でなければなりません(コンパイル時に決まる必要があります)。
制約:p < 2^31。inv、/、fft、primitive_rootは、pが素数であることを要します。それ以外は、pが素数でなくても動きます。
法が実行時に動的に変わる場合は、CPLib.Arithmeticのadd_mod・sub_mod・mul_mod・pow_mod・inv_modを使ってください。
法pは型パラメータとして与えます。例として、p = 17 としたい場合は、
- 空の型(フィールドを持たないunboxedな型)
P17を作ります:type P17 = unbox struct {} P17 : PrimeProviderを実装し、PrimeProvider::value関数で17を返すようにします:value = |_| 17_U32;
するとZP P17が環"Z/(17)"を表す型になります。
いくつかの有名な素数nに対するPrimeProviderの型Pnは、このモジュールに定義されています。
使用例:
import CPLib.ZP;
type P17 = unbox struct {};
impl P17 : PrimeProvider {
create = P17 {};
value = |_| 17_U32;
}
main : IO () = (
let x = zp(-5) : ZP P17;
let y = x * x;
assert_eq(|_|"", y.@value, 8_U32) // (-5)*(-5) = 25 = 8 mod 17
);
Values
namespace CPLib.ZP
fft
Type: [p : CPLib.ZP::PrimeProvider] CPLib.ZP::FFTDirection -> Std::Array (CPLib.ZP::ZP p) -> Std::Array (CPLib.ZP::ZP p)
ZP p型の配列に対して高速フーリエ変換を行う
入力の長さを2のべき乗に切り上げ、末尾を0で埋めてから変換する。返る配列の長さは切り上げた長さである(長さ3なら4)。順変換して逆変換すると、元の配列の末尾に0を足した、切り上げた長さの配列が返る。
制約:2^c | (p-1) かつ |x| <= 2^c なる c が存在する
計算量:O(n log n + sqrt(p))、n = |x|。pがこのモジュールに定義されている素数ならO(n log n)
Parameters
dir: FFTの方向(順方向か逆方向か)x:ZP p型の配列
inv
Type: [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p -> CPLib.ZP::ZP p
ZP pの逆元を求める。
0を与えた場合はプログラムを終了する。
計算量:O(log p)
Parameters
x:ZP p型の整数
make
Deprecated: Use CPLib.ZP::zp instead.
Type: [p : CPLib.ZP::PrimeProvider] Std::I64 -> CPLib.ZP::ZP p
zpの別名(非推奨)
primitive_root
Type: [p : CPLib.ZP::PrimeProvider] CPLib.ZP::ZP p
法pの原始根を一つ得る
計算量:O(sqrt(p))。pがこのモジュールに定義されている素数ならO(1)
zp
Type: [p : CPLib.ZP::PrimeProvider] Std::I64 -> CPLib.ZP::ZP p
I64からZP pの値を作成する
計算量:O(1)
Parameters
x:I64型の整数
namespace CPLib.ZP::PrimeProvider
create
Type: [p : CPLib.ZP::PrimeProvider] p
Trait member of CPLib.ZP::PrimeProvider
value
Type: [p : CPLib.ZP::PrimeProvider] p -> Std::U32
Trait member of CPLib.ZP::PrimeProvider
namespace CPLib.ZP::ZP
@prime
Type: CPLib.ZP::ZP p -> p
xの法pを与えるPrimeProviderの値を返す
Parameters
x:ZP p型の整数
@value
Type: CPLib.ZP::ZP p -> Std::U32
xを[0, p)の整数として返す
Parameters
x:ZP p型の整数
Types and aliases
namespace CPLib.ZP
FFTDirection
Defined as: type FFTDirection = unbox union { ...variants... }
高速フーリエ変換の方向(順方向か逆方向か)を表す型
variant forward
Type: ()
variant inverse
Type: ()
P1000000007
Defined as: type P1000000007 = unbox struct { ...fields... }
P1000000009
Defined as: type P1000000009 = unbox struct { ...fields... }
P167772161
Defined as: type P167772161 = unbox struct { ...fields... }
NTT-friendly prime (2^25 | p-1)
P469762049
Defined as: type P469762049 = unbox struct { ...fields... }
NTT-friendly prime (2^26 | p-1)
P754974721
Defined as: type P754974721 = unbox struct { ...fields... }
NTT-friendly prime (2^24 | p-1)
P998244353
Defined as: type P998244353 = unbox struct { ...fields... }
NTT-friendly prime (2^23 | p-1)
ZP
Defined as: type ZP p = unbox struct { ...fields... }
素数pを法とする整数の環
Traits and aliases
namespace CPLib.ZP
trait p : PrimeProvider
method create
Type: p
method value
Type: p -> Std::U32