// competitive-verifier: STANDALONE
#include "Math/mod_power.hpp"
#include <bits/stdc++.h>
using namespace std;
int greedy_solve(int x, int n, int mod)
{
int ans = 1;
for (int i = 0; i < n; i++)
{
ans *= x;
}
while (ans < 0)
{
ans += mod;
}
return ans % mod;
}
int solve(int x, int n, int mod)
{
return mod_pow<long long>(x, n, mod);
}
int main()
{
for (int x = -10; x <= 0; x++)
{
for (int n = 0; n <= 5; n++)
{
assert(solve(x, n, 1000000) == greedy_solve(x, n, 1000000));
}
}
return 0;
}
#line 1 "test/Math/mod_power/my_test.cpp"
// competitive-verifier: STANDALONE
#line 1 "Math/mod_power.hpp"
#include <bits/stdc++.h>
using namespace std;
#line 2 "Other/fast_power.hpp"
using namespace std;
template <class S>
S fast_pow(S x, long long n, function<S(S, S)> mul, function<S()> e)
{
assert(0 <= n);
S ans = e();
while (n)
{
if (n & 1)
{
ans = mul(ans, x);
}
x = mul(x, x);
n >>= 1;
}
return ans;
}
#line 5 "Math/mod_power.hpp"
template <typename T>
enable_if_t<is_integral_v<T> || is_same_v<T, __int128_t>, T>
mod_pow(T x, T n, T mod)
{
assert(0 <= n);
assert(0 < mod);
assert(mod <= numeric_limits<T>::max() / mod);
x %= mod;
if (x < 0)
{
x += mod;
}
auto mul = [&](T a, T b) -> T
{
return (a * b) % mod;
};
auto e = [&]() -> T
{
return 1;
};
return fast_pow<T>(x, n, mul, e);
}
#line 5 "test/Math/mod_power/my_test.cpp"
using namespace std;
int greedy_solve(int x, int n, int mod)
{
int ans = 1;
for (int i = 0; i < n; i++)
{
ans *= x;
}
while (ans < 0)
{
ans += mod;
}
return ans % mod;
}
int solve(int x, int n, int mod)
{
return mod_pow<long long>(x, n, mod);
}
int main()
{
for (int x = -10; x <= 0; x++)
{
for (int n = 0; n <= 5; n++)
{
assert(solve(x, n, 1000000) == greedy_solve(x, n, 1000000));
}
}
return 0;
}
test/Math/mod_power/my_test.cpp