cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Oxojo/cp-library

:heavy_check_mark: library/math/modula.hpp

Depends on

Required by

Verified with

Code

#pragma once

#include "../template/template.hpp"

ll modmul(ll a, ll b, ll mod) { return __int128(a) * b % mod; }
ll modpow(ll a, ll b, ll mod) {
  ll ans = 1;
  for (; b; a = modmul(a, a, mod), b /= 2)
    if (b & 1) ans = modmul(ans, a, mod);
  return ans;
}
// a^x == b (mod p), if no such x exists than -1
ll modlog(ll a, ll b, ll p) {
    ll n = (ll)sqrtl(p) + 1, e = 1, f = 1, j = 1;
    unordered_map<ll, ll> A;
    while (j = n && (e = f = e * a % p) != b % p)
        A[e * b % p] = j++;
    if (e == b % p) return j;
    if (gcd(p, e) == gcd(p, b))
        reps(i, 2, n + 2) if (A.count(e = e * f % p)) 
            return n * i - A[e];
    return -1;
}
// x^2 == a (mod p)
ll modsqrt(ll a, ll p) {
    a %= p;
    while (a < 0) a += p;
    if (a == 0) return 0;
    if (modpow(a, (p - 1) / 2, p) != 1) return -1;
    if (p % 4 == 3) return modpow(a, (p + 1) / 4, p);
    ll s = p - 1, n = 2;
    ll r = 0, m;
    while (s % 2 == 0) ++r, s /= 2;
    while (modpow(n, (p - 1) / 2, p) != p - 1) ++n;
    ll x = modpow(a, (s + 1) / 2, p);
    ll b = modpow(a, s, p), g = modpow(n, s, p);
    for (;; r = m) {
        ll t = b;
        for (m = 0; m < r && t != 1; ++m) t = modmul(t, t, p);
        if (m == 0) return x;
        ll gs = modpow(g, 1ll << (r - m - 1), p);
        g = modmul(gs, gs, p);
        x = modmul(x, gs, p);
        b = modmul(b, g, p);
    }
}
ll modinv(ll x, ll mod) { return modpow(x, mod - 2, mod); }
#line 2 "library/math/modula.hpp"

#line 2 "library/template/template.hpp"

#include <bits/stdc++.h>
using namespace std;
#define MM << ' ' <<
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for(ll i = 0; i < (r); i++)
#define reps(i, l, r) for(ll i = (l); i < (r); i++)
#define rrep(i, l, r) for(ll i = (r) - 1; i >= l; i--)
template <class T> void uniq(T &a) { sort(all(a)); erase(unique(all(a)), a.end()); }
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
const ll INF = numeric_limits<ll>::max() / 4;
const ld inf = numeric_limits<ld>::max() / 2;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;
const ld pi = 3.141592653589793238;
template <class T> void rev(T &a) { reverse(all(a)); }
ll popcnt(ll a) { return __builtin_popcountll(a); }
template<typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template<typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	os << p.first << " " << p.second;
	return os;
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
	is >> p.first >> p.second;
	return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vec<T>& v) {
	rep(i, sz(v)) {
		os << v[i] << " \n"[i + 1 == sz(v)];
	}
	return os;
}
template <typename T>
istream& operator>>(istream& is, vec<T>& v) {
	for (T& in : v) is >> in;
	return is;
}
void yesno(bool t) {
	cout << (t ? "Yes" : "No") << endl;
}
#line 4 "library/math/modula.hpp"

ll modmul(ll a, ll b, ll mod) { return __int128(a) * b % mod; }
ll modpow(ll a, ll b, ll mod) {
  ll ans = 1;
  for (; b; a = modmul(a, a, mod), b /= 2)
    if (b & 1) ans = modmul(ans, a, mod);
  return ans;
}
// a^x == b (mod p), if no such x exists than -1
ll modlog(ll a, ll b, ll p) {
    ll n = (ll)sqrtl(p) + 1, e = 1, f = 1, j = 1;
    unordered_map<ll, ll> A;
    while (j = n && (e = f = e * a % p) != b % p)
        A[e * b % p] = j++;
    if (e == b % p) return j;
    if (gcd(p, e) == gcd(p, b))
        reps(i, 2, n + 2) if (A.count(e = e * f % p)) 
            return n * i - A[e];
    return -1;
}
// x^2 == a (mod p)
ll modsqrt(ll a, ll p) {
    a %= p;
    while (a < 0) a += p;
    if (a == 0) return 0;
    if (modpow(a, (p - 1) / 2, p) != 1) return -1;
    if (p % 4 == 3) return modpow(a, (p + 1) / 4, p);
    ll s = p - 1, n = 2;
    ll r = 0, m;
    while (s % 2 == 0) ++r, s /= 2;
    while (modpow(n, (p - 1) / 2, p) != p - 1) ++n;
    ll x = modpow(a, (s + 1) / 2, p);
    ll b = modpow(a, s, p), g = modpow(n, s, p);
    for (;; r = m) {
        ll t = b;
        for (m = 0; m < r && t != 1; ++m) t = modmul(t, t, p);
        if (m == 0) return x;
        ll gs = modpow(g, 1ll << (r - m - 1), p);
        g = modmul(gs, gs, p);
        x = modmul(x, gs, p);
        b = modmul(b, g, p);
    }
}
ll modinv(ll x, ll mod) { return modpow(x, mod - 2, mod); }
Back to top page