This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 離散対数問題 (Discrete Logarithm Problem) を解く
// a^x = b (mod p, p は素数) を満たすような x (1 <= x <= p-1) を求める
template <typename NumType>
struct DiscreteLogarithm {
unordered_map<NumType, NumType> pow_table_;
// a と p をコンストラクタで指定すると、pow_table_ が作られる
DiscreteLogarithm() : pow_table_() {}
DiscreteLogarithm(NumType a, NumType p, double ratio=0.5) {
set_rec_table(a, p, ratio);
}
NumType mod_pow(NumType x, NumType k, NumType p) {
NumType res = 1;
for(; k>0; k>>=1) {
if(k & 1) (res *= x) %= p;
(x *= x) %= p;
}
return res;
}
NumType mod_inv(NumType x, NumType p) {
return mod_pow(x, p-2, p);
}
// a^{-s * sqrtp} => s が格納された map を返す
unordered_map<NumType, NumType> get_rec_table(NumType a, NumType p, double ratio=0.5) {
unordered_map<NumType, NumType> num_rec;
NumType sp = pow(p, ratio) + 1;
NumType tp = pow(p, 1.0 - ratio) + 1;
// a^{-sqrtp}
NumType inv_pow_a = mod_inv(mod_pow(a, sp, p), p);
// a^{-s * sqrtp}
NumType mul = 1;
for(NumType s=0; s<=tp; s++) {
NumType key = mul;
if(num_rec.count(key)) break;
num_rec[key] = s;
(mul *= inv_pow_a) %= p;
}
return num_rec;
}
// pow_table_ に map をセットする
void set_rec_table(NumType a, NumType p, double ratio) {
pow_table_ = get_rec_table(a, p, ratio);
}
// Baby-step Giant-step Algorithm: O(sqrt(p)) だが ratio に依存
// a^{-s * sp} の map は、直前のものを使いまわすこともできる
// pow_table_ が空の場合、または use_same_table が指定されていない場合は自動的に map が作られ、それが pow_table_ に保存される
NumType BSGS(NumType a, NumType b, NumType p, bool use_same_table=false, double ratio=0.5) {
a %= p, b %= p;
NumType sp = pow(p, ratio) + 1;
// a^{-s * sp} => s
unordered_map<NumType, NumType> &num_rec = pow_table_;
if(num_rec.empty() or !use_same_table) {
set_rec_table(a, p, ratio);
}
// a^t * b^{-1} = a^{-s * sp}
// この時の答えは s * sp + t
NumType mul = mod_inv(b, p);
for(NumType t=0; t<=sp; t++) {
if(num_rec.count(mul)) {
NumType s = num_rec[mul];
// 解の範囲は 1 以上 p-1 以下なのでそれはチェックが必要
NumType ans = s * sp + t;
if(1 <= ans and ans <= p-1) return ans;
}
(mul *= a) %= p;
}
// 解なし
return NumType(-1);
}
};
#line 1 "math/math_014_bsgs.cpp"
// 離散対数問題 (Discrete Logarithm Problem) を解く
// a^x = b (mod p, p は素数) を満たすような x (1 <= x <= p-1) を求める
template <typename NumType>
struct DiscreteLogarithm {
unordered_map<NumType, NumType> pow_table_;
// a と p をコンストラクタで指定すると、pow_table_ が作られる
DiscreteLogarithm() : pow_table_() {}
DiscreteLogarithm(NumType a, NumType p, double ratio=0.5) {
set_rec_table(a, p, ratio);
}
NumType mod_pow(NumType x, NumType k, NumType p) {
NumType res = 1;
for(; k>0; k>>=1) {
if(k & 1) (res *= x) %= p;
(x *= x) %= p;
}
return res;
}
NumType mod_inv(NumType x, NumType p) {
return mod_pow(x, p-2, p);
}
// a^{-s * sqrtp} => s が格納された map を返す
unordered_map<NumType, NumType> get_rec_table(NumType a, NumType p, double ratio=0.5) {
unordered_map<NumType, NumType> num_rec;
NumType sp = pow(p, ratio) + 1;
NumType tp = pow(p, 1.0 - ratio) + 1;
// a^{-sqrtp}
NumType inv_pow_a = mod_inv(mod_pow(a, sp, p), p);
// a^{-s * sqrtp}
NumType mul = 1;
for(NumType s=0; s<=tp; s++) {
NumType key = mul;
if(num_rec.count(key)) break;
num_rec[key] = s;
(mul *= inv_pow_a) %= p;
}
return num_rec;
}
// pow_table_ に map をセットする
void set_rec_table(NumType a, NumType p, double ratio) {
pow_table_ = get_rec_table(a, p, ratio);
}
// Baby-step Giant-step Algorithm: O(sqrt(p)) だが ratio に依存
// a^{-s * sp} の map は、直前のものを使いまわすこともできる
// pow_table_ が空の場合、または use_same_table が指定されていない場合は自動的に map が作られ、それが pow_table_ に保存される
NumType BSGS(NumType a, NumType b, NumType p, bool use_same_table=false, double ratio=0.5) {
a %= p, b %= p;
NumType sp = pow(p, ratio) + 1;
// a^{-s * sp} => s
unordered_map<NumType, NumType> &num_rec = pow_table_;
if(num_rec.empty() or !use_same_table) {
set_rec_table(a, p, ratio);
}
// a^t * b^{-1} = a^{-s * sp}
// この時の答えは s * sp + t
NumType mul = mod_inv(b, p);
for(NumType t=0; t<=sp; t++) {
if(num_rec.count(mul)) {
NumType s = num_rec[mul];
// 解の範囲は 1 以上 p-1 以下なのでそれはチェックが必要
NumType ans = s * sp + t;
if(1 <= ans and ans <= p-1) return ans;
}
(mul *= a) %= p;
}
// 解なし
return NumType(-1);
}
};