a^n=b(mod m)となる最小のnを求める (daylight/math/modlog.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/math/modlog.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)

Code

#include <atcoder/all>
#include "daylight/base.hpp"
using namespace atcoder;

/// @brief a^n=b(mod m)となる最小のnを求める
/// @param a パラメータ
/// @param b パラメータ
/// @param m 除数
/// @return nが存在しない場合-1,存在する場合n
ll modlog(ll a, ll b, ll m) {
	a %= m;
	b %= m;
	if(a == 0) {
		if(b == 1)
			return 0;
		else if(b == 0)
			return 1;
		else
			return -1;
	}
	if(b == 1) {
		return 0;
	}
	ll sq = 1;
	while(sq * sq < m) sq++;
	map<ll, ll> A;
	ll cur = a;
	FOR(r, 1, sq) {
		if(!A.count(cur)) A[cur] = r;
		cur *= a;
		cur %= m;
	}
	using mint = modint;
	mint::set_mod(m);
	ll a_powM = mint(a).inv().pow(sq).val();
	cur = b;
	REP(q, sq) {
		if(cur == 1 && q > 0) return q * sq;
		if(A.count(cur)) return q * sq + A[cur];
		cur *= a_powM;
		cur %= m;
	}
	return -1;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page