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

generalized_discrete_logarithm
(math/generalized_discrete_logarithm.hpp)

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

generalized_discrete_logarithm

使い方

template<typename T> generalized_discrete_logarithm(T x, T y, auto f, int n, auto f_m, int m) : $f^n(x) = y$ を満たす $n$ 以下の自然数 $k$ が存在するかどうかを判定し、存在するならその最小値を返す（存在しない場合は $-1$ が返る）。適切な $m$ の設定で$O(\sqrt{N})$

ただし、

• $f$ の計算は $\Theta(T)$ 時間かかるとする。
• ある自然数 $m$ ($\sqrt{N}$ 程度が好ましい) について、$f^m(x)$ も $\Theta(T)$ 時間で求められるとする。

参考

[250225離散対数問題](https://acompany-ac.notion.site/250225-1a4269d8558680a8bcbef0b561d04a41)

Verified with

• verify/yosupo/generalized_discrete_logarithm.test.cpp

Code

#pragma once

#include<unordered_set>

template<typename T>
T generalized_discrete_logarithm(T x, T y, auto f, int n, auto f_m, int m){
	if(x == y){
		return 0;
	}

	std::unordered_set<T> baby_steps;
	T fy = y;
	for(int i = 0;i < m;i++){
		baby_steps.insert(fy);
		fy = f(fy);
	}

	T fx = x;
	bool is_first_loop = true;
	for(int i = 0;i <= n;i += m){
		T next_val = f_m(fx);
		if(baby_steps.contains(next_val)){
			for(int j = i+1;j <= i+m;j++){
				fx = f(fx);
				if(fx == y){
					return (j <= n ? j : -1);
				}
			}
			if(is_first_loop){
				is_first_loop = false;
			}else{
				return -1;
			}
		}
		fx = next_val;
	}
	return -1;
}

#line 2 "math/generalized_discrete_logarithm.hpp"

#include<unordered_set>

template<typename T>
T generalized_discrete_logarithm(T x, T y, auto f, int n, auto f_m, int m){
	if(x == y){
		return 0;
	}

	std::unordered_set<T> baby_steps;
	T fy = y;
	for(int i = 0;i < m;i++){
		baby_steps.insert(fy);
		fy = f(fy);
	}

	T fx = x;
	bool is_first_loop = true;
	for(int i = 0;i <= n;i += m){
		T next_val = f_m(fx);
		if(baby_steps.contains(next_val)){
			for(int j = i+1;j <= i+m;j++){
				fx = f(fx);
				if(fx == y){
					return (j <= n ? j : -1);
				}
			}
			if(is_first_loop){
				is_first_loop = false;
			}else{
				return -1;
			}
		}
		fx = next_val;
	}
	return -1;
}

Back to top page