結果
| 問題 | No.3522 冪乗乗 |
| コンテスト | |
| ユーザー |
👑  binap
|
| 提出日時 | 2025-02-09 15:41:59 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,288 bytes |
| 記録 | |
| コンパイル時間 | 4,916 ms |
| コンパイル使用メモリ | 280,324 KB |
| 実行使用メモリ | 30,320 KB |
| 平均クエリ数 | 30.90 |
| 最終ジャッジ日時 | 2026-05-01 20:59:14 |
| 合計ジャッジ時間 | 11,815 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 37 WA * 26 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef long double ld;
typedef pair<int, int> P;
template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}
template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}
template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}
template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;}
template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> void chmin(T& a, T b){a = min(a, b);}
template<typename T> void chmax(T& a, T b){a = max(a, b);}
// Start 14:59
// Fermat's little theorem and Euler's theorem
//(I) N = 0 mod B
// M^L = 0 (M = 0 and L > 0)
// M^L != 0 (M != 0 or(M = 0 and L = 0))
// N^(M^L) = 1 (M = 0 and L > 0)
// N^(M^L) = 0 (M != 0 or(M = 0 and L = 0))
//(II) B = 1
// ans = 1
//(III) otherwise
// a^(phi(B)) = 1 mod(B)
// a^(phi(phi(B))) = 1 mod(phi(B))
// Start Implementation 15:15
// montgomery modint (MOD < 2^62, MOD is odd)
struct MontgomeryModInt64 {
using mint = MontgomeryModInt64;
using u64 = uint64_t;
using u128 = __uint128_t;
// static menber
static u64 MOD;
static u64 INV_MOD; // INV_MOD * MOD ≡ 1 (mod 2^64)
static u64 T128; // 2^128 (mod MOD)
// inner value
u64 val;
// constructor
MontgomeryModInt64() : val(0) { }
MontgomeryModInt64(long long v) : val(reduce((u128(v) + MOD) * T128)) { }
u64 get() const {
u64 res = reduce(val);
return res >= MOD ? res - MOD : res;
}
// mod getter and setter
static u64 get_mod() { return MOD; }
static void set_mod(u64 mod) {
assert(mod < (1LL << 62));
assert((mod & 1));
MOD = mod;
T128 = -u128(mod) % mod;
INV_MOD = get_inv_mod();
}
static u64 get_inv_mod() {
u64 res = MOD;
for (int i = 0; i < 5; ++i) res *= 2 - MOD * res;
return res;
}
static u64 reduce(const u128 &v) {
return (v + u128(u64(v) * u64(-INV_MOD)) * MOD) >> 64;
}
// arithmetic operators
mint operator - () const { return mint() - mint(*this); }
mint operator + (const mint &r) const { return mint(*this) += r; }
mint operator - (const mint &r) const { return mint(*this) -= r; }
mint operator * (const mint &r) const { return mint(*this) *= r; }
mint operator / (const mint &r) const { return mint(*this) /= r; }
mint& operator += (const mint &r) {
if ((val += r.val) >= 2 * MOD) val -= 2 * MOD;
return *this;
}
mint& operator -= (const mint &r) {
if ((val += 2 * MOD - r.val) >= 2 * MOD) val -= 2 * MOD;
return *this;
}
mint& operator *= (const mint &r) {
val = reduce(u128(val) * r.val);
return *this;
}
mint& operator /= (const mint &r) {
*this *= r.inv();
return *this;
}
mint inv() const { return pow(MOD - 2); }
mint pow(u128 n) const {
mint res(1), mul(*this);
while (n > 0) {
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
// other operators
bool operator == (const mint &r) const {
return (val >= MOD ? val - MOD : val) == (r.val >= MOD ? r.val - MOD : r.val);
}
bool operator != (const mint &r) const {
return (val >= MOD ? val - MOD : val) != (r.val >= MOD ? r.val - MOD : r.val);
}
friend istream& operator >> (istream &is, mint &x) {
long long t;
is >> t;
x = mint(t);
return is;
}
friend ostream& operator << (ostream &os, const mint &x) {
return os << x.get();
}
friend mint modpow(const mint &r, long long n) {
return r.pow(n);
}
friend mint modinv(const mint &r) {
return r.inv();
}
};
typename MontgomeryModInt64::u64
MontgomeryModInt64::MOD, MontgomeryModInt64::INV_MOD, MontgomeryModInt64::T128;
template<typename T>
T pow_mod(T A, T N, T MOD){
T res = 1 % MOD;
A %= MOD;
while(N){
if(N & 1) res = (res * A) % MOD;
A = (A * A) % MOD;
N >>= 1;
}
return res;
}
bool MillerRabin(long long N, vector<long long> A){
using mint = MontgomeryModInt64;
mint::set_mod(N);
long long s = 0, d = N - 1;
while(d % 2 == 0){
s++;
d >>= 1;
}
for(auto a : A){
if(N <= a) return true;
mint x = mint(a).pow(d);
if(x != 1){
long long t;
for(t = 0; t < s; t++){
if(x == N - 1) break;
x *= x;
}
if(t == s) return false;
}
}
return true;
};
bool is_prime(long long N){
if(N <= 1) return false;
if(N == 2) return true;
if(N % 2 == 0) return false;
if(N < 4759123141LL) return MillerRabin(N, {2, 7, 61});
else return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
};
vector<long long> prime_factor(long long N){
assert(N >= 1);
using u128 = __uint128_t;
vector<long long> res;
vector<long long> calc;
while(N % 2 == 0){
N /= 2;
res.push_back(2);
}
if(N == 1) return res;
calc.push_back(N);
while(calc.size()){
long long N = calc.back(); calc.pop_back();
long long x, y, c, g;
auto f = [&](long long x){return (u128(x) * x + c) % N;};
while(!is_prime(N)){
x = rand() % N; y = x;
c = (rand() % (N - 1)) + 1;
g = 1;
while(g == 1){
x = f(x);
y = f(f(y));
g = gcd(abs(x - y), N);
}
if(g == N) continue;
if(is_prime(N / g)) res.push_back(N / g);
else calc.push_back(N / g);
N = g;
}
res.push_back(N);
}
return res;
};
// https://ei1333.github.io/luzhiled/snippets/math/mod-pow.html
template< typename T >
T mod_pow(T x, T n, const T &p) {
T ret = 1;
while(n > 0) {
if(n & 1) (ret *= x) %= p;
(x *= x) %= p;
n >>= 1;
}
return ret;
}
int main(){
int n, m, l;
cin >> n >> m >> l;
int b = -1;
{
// ok >= b, ng < b
int ok = 1000000001, ng = 0;
while(ok - ng > 1){
int mid = (ok + ng) / 2;
cout << "? " << mid << ' ' << 1 << "\n";
flush(cout);
int res;
cin >> res;
if(res < mid) ok = mid;
else ng = mid;
}
b = ok;
}
auto phi = [&](int x){
auto primes = prime_factor(x);
sort(primes.begin(), primes.end());
primes.erase(unique(primes.begin(), primes.end()), primes.end());
for(int p : primes){
x /= p;
x *= p - 1;
}
return x;
};
auto phib = phi(b);
// auto phiphib = phi(phib);
n %= b;
if(n == 0){
if(m == 0 and l > 0) cout << "! 1\n";
else cout << "! 0 \n";
return 0;
}
int e = mod_pow<long long>(m, l, phib);
int ans = mod_pow<long long>(n, e, b);
cout << "! " << ans << "\n";
return 0;
}