結果
| 問題 | No.981 一般冪乗根 |
| ユーザー |
 Haar
|
| 提出日時 | 2026-07-13 19:39:04 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 1,590 ms / 6,000 ms |
| + 806µs | |
| コード長 | 22,004 bytes |
| 記録 | |
| コンパイル時間 | 15,735 ms |
| コンパイル使用メモリ | 226,992 KB |
| 実行使用メモリ | 9,312 KB |
| 最終ジャッジ日時 | 2026-07-13 19:40:16 |
| 合計ジャッジ時間 | 51,215 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 RE * 14 |
ソースコード
// Bundled at 2026/07/13 19:37:14 +09:00
// Author: Haar
pub mod main {
use super::*;
#[allow(unused_imports)]
use haar_lib::{get, input, io::fastio::*, iter::join_str::*, output};
#[allow(unused_imports)]
use std::cell::{Cell, RefCell};
#[allow(unused_imports)]
use std::cmp::{max, min, Reverse};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::Write;
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::rc::Rc;
pub struct Problem {
io: FastIO,
}
use haar_lib::math::mod_ops::root::*;
impl Problem {
pub fn init() -> Self {
Self { io: FastIO::new() }
}
pub fn main(&mut self) {
let t = self.io.read_usize();
for _ in 0..t {
let p = self.io.read_u64();
let k = self.io.read_u64();
let a = self.io.read_u64();
let ans = mod_kth_root(a, k, p);
if let Some(ans) = ans {
self.io.writeln(ans);
} else {
self.io.writeln(-1);
}
}
}
}
}
fn main() {
std::thread::Builder::new()
.spawn(|| main::Problem::init().main())
.unwrap()
.join()
.unwrap()
}
use crate as haar_lib;
pub mod io {
pub mod fastio {
use std::fmt::Display;
use std::io::{Read, Write};
pub struct FastIO {
in_bytes: Vec<u8>,
in_cur: usize,
out_buf: std::io::BufWriter<std::io::Stdout>,
}
impl FastIO {
pub fn new() -> Self {
let mut s = vec![];
std::io::stdin().read_to_end(&mut s).unwrap();
let cout = std::io::stdout();
Self {
in_bytes: s,
in_cur: 0,
out_buf: std::io::BufWriter::new(cout),
}
}
#[inline]
pub fn getc(&mut self) -> Option<u8> {
let c = *self.in_bytes.get(self.in_cur)?;
self.in_cur += 1;
Some(c)
}
#[inline]
pub fn peek(&self) -> Option<u8> {
Some(*self.in_bytes.get(self.in_cur)?)
}
#[inline]
pub fn skip(&mut self) {
while self.peek().is_some_and(|c| c.is_ascii_whitespace()) {
self.in_cur += 1;
}
}
pub fn read_u64(&mut self) -> u64 {
self.skip();
let mut ret: u64 = 0;
while self.peek().is_some_and(|c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
self.in_cur += 1;
}
ret
}
pub fn read_u32(&mut self) -> u32 {
self.read_u64() as u32
}
pub fn read_usize(&mut self) -> usize {
self.read_u64() as usize
}
pub fn read_i64(&mut self) -> i64 {
self.skip();
let mut ret: i64 = 0;
let minus = if self.peek() == Some(b'-') {
self.in_cur += 1;
true
} else {
false
};
while self.peek().is_some_and(|c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
self.in_cur += 1;
}
if minus {
ret = -ret;
}
ret
}
pub fn read_i32(&mut self) -> i32 {
self.read_i64() as i32
}
pub fn read_isize(&mut self) -> isize {
self.read_i64() as isize
}
pub fn read_f64(&mut self) -> f64 {
self.read_chars()
.into_iter()
.collect::<String>()
.parse()
.unwrap()
}
pub fn read_chars(&mut self) -> Vec<char> {
self.read_bytes().into_iter().map(Into::into).collect()
}
pub fn read_string(&mut self) -> String {
self.read_chars().into_iter().collect()
}
pub fn read_bytes(&mut self) -> Vec<u8> {
self.skip();
let mut ret = vec![];
while self.peek().is_some_and(|c| c.is_ascii_graphic()) {
ret.push(self.in_bytes[self.in_cur]);
self.in_cur += 1;
}
ret
}
pub fn read_char(&mut self) -> char {
self.skip();
self.getc().unwrap().into()
}
pub fn writeln_u32(&mut self, mut n: u32) {
if n == 0 {
self.out_buf.write_all(b"0\n").unwrap();
return;
}
let mut buf = [b' '; 10];
let mut i = 9;
while n > 0 {
buf[i] = (n % 10) as u8 + b'0';
n /= 10;
i -= 1;
}
self.out_buf.write_all(&buf).unwrap();
self.out_buf.write_all(b"\n").unwrap();
}
pub fn write<T: Display>(&mut self, s: T) {
self.out_buf.write_all(s.to_string().as_bytes()).unwrap();
}
pub fn write_rev<T: Display>(&mut self, s: T) {
let mut s = s.to_string().as_bytes().to_vec();
s.reverse();
self.out_buf.write_all(&s).unwrap();
}
pub fn writeln<T: Display>(&mut self, s: T) {
self.write(s);
self.out_buf.write_all(b"\n").unwrap();
}
pub fn writeln_rev<T: Display>(&mut self, s: T) {
self.write_rev(s);
self.out_buf.write_all(b"\n").unwrap();
}
pub fn write_bytes(&mut self, s: &[u8]) {
self.out_buf.write_all(s).unwrap();
}
pub fn writeln_intersperse<I>(&mut self, it: I)
where
I: IntoIterator,
I::Item: Display,
{
let mut it = it.into_iter();
if let Some(s) = it.next() {
self.write(s);
}
for s in it {
self.write_bytes(b" ");
self.write(s);
}
self.write_bytes(b"\n");
}
}
impl Drop for FastIO {
fn drop(&mut self) {
self.out_buf.flush().unwrap();
}
}
}
}
pub mod iter {
pub mod join_str {
pub trait JoinStr: Iterator {
fn join_str(self, s: &str) -> String
where
Self: Sized,
Self::Item: ToString,
{
self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
}
}
impl<I> JoinStr for I where I: Iterator + ?Sized {}
}
}
pub mod macros {
pub mod io {
#[macro_export]
macro_rules! get {
( $in:expr; [$a:tt $(as $to:ty)*; $num:expr] ) => {
(0..$num).map(|_| get!($in; $a $(as $to)*)).collect::<Vec<_>>()
};
( $in:expr; ($($type:tt $(as $to:ty)*),*) ) => {
($(get!($in; $type $(as $to)*)),*)
};
( $in:expr; i8 ) => { $in.read_i64() as i8 };
( $in:expr; i16 ) => { $in.read_i64() as i16 };
( $in:expr; i32 ) => { $in.read_i64() as i32 };
( $in:expr; i64 ) => { $in.read_i64() };
( $in:expr; isize ) => { $in.read_i64() as isize };
( $in:expr; u8 ) => { $in.read_u64() as u8 };
( $in:expr; u16 ) => { $in.read_u64() as u16 };
( $in:expr; u32 ) => { $in.read_u64() as u32 };
( $in:expr; u64 ) => { $in.read_u64() };
( $in:expr; usize ) => { $in.read_u64() as usize };
( $in:expr; char) => { $in.read_char() };
( $in:expr; [u8]) => { $in.read_bytes() };
( $in:expr; [char] ) => { $in.read_chars() };
( $in:expr; String ) => { $in.read_string() };
( $in:expr; $from:tt as $to:ty ) => { <$to>::from(get!($in; $from)) };
}
#[macro_export]
macro_rules! input {
( @inner $in:expr, $name:pat, $type:tt ) => {
let $name = get!($in; $type);
};
( @inner $in:expr, $name:pat, $type:tt as $to:ty ) => {
let $name = get!($in; $type as $to);
};
( $in:expr; $( $names:pat = $type:tt $(as $to:ty)? ),* ) => {
$(input!(@inner $in, $names, $type $(as $to)?);)*
}
}
#[macro_export]
macro_rules! output {
( @one $io:expr, $a:expr ) => {
$io.write($a);
};
( $io:expr; $a:expr, $($rest:expr),* ) => {
output!(@one $io, $a);
$(
$io.write(" ");
$io.write($rest);
)*
$io.writeln("");
};
}
}
}
pub mod math {
pub mod factorize {
pub mod pollard_rho {
use crate::math::{gcd_lcm::*, montgomery::*, primality::miller_rabin::*};
fn find_factor(n: u64, a: u64) -> Option<u64> {
assert!(n % 2 == 1);
let mn = Montgomery::new(n);
let f = |x| mn.add(mn.mul(x, x), Wrapped(a));
let mut x = mn.wrap(a);
let mut y = f(x);
loop {
x = f(x);
y = f(f(y));
let x = mn.unwrap(x);
let y = mn.unwrap(y);
let d = x.abs_diff(y).gcd(n);
if d == 1 {
continue;
}
return (d < n).then_some(d);
}
}
pub fn pollard_rho(mut n: u64) -> Vec<u64> {
assert!(n > 0);
if n == 1 {
return vec![];
}
let mut ret = vec![];
while n % 2 == 0 {
ret.push(2);
n /= 2;
}
let mut remain = vec![n];
while let Some(n) = remain.pop() {
if n == 1 {
continue;
}
if MillerRabin.is_prime(n) {
ret.push(n);
continue;
}
if let Some(p) = (1..).find_map(|a| find_factor(n, a)) {
remain.push(n / p);
remain.push(p);
}
}
ret.sort();
ret
}
}
}
pub mod gcd_lcm {
use std::mem::swap;
pub trait GcdLcm {
type Output;
fn gcd(self, _: Self::Output) -> Self::Output;
fn lcm(self, _: Self::Output) -> Self::Output;
fn gcd_lcm(self, _: Self::Output) -> (Self::Output, Self::Output);
}
macro_rules! gcd_lcm_impl_all {
( $($t:ty),* ) => {
$(
impl GcdLcm for $t {
type Output = $t;
fn gcd(self, mut b: Self::Output) -> Self::Output {
let mut a = self;
if a < b {
swap(&mut a, &mut b);
}
if b == 0 {
return a;
}
b.gcd(a % b)
}
fn lcm(self, b: Self::Output) -> Self::Output {
self / self.gcd(b) * b
}
fn gcd_lcm(self, b: Self::Output) -> (Self::Output, Self::Output) {
let g = self.gcd(b);
(g, self / g * b)
}
}
)*
}
}
gcd_lcm_impl_all!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
}
pub mod mod_ops {
pub mod inv {
use crate::math::gcd_lcm::GcdLcm;
pub fn mod_inv(mut a: u64, m: u64) -> Option<u64> {
assert!(
0 < m && m <= 0xFFFFFFFF,
"Violated 0 < m <= 0xFFFFFFFF (m = {m})"
);
if a >= m {
a %= m;
}
if a.gcd(m) != 1 {
return None;
}
let mut b = m;
let mut u = 1;
let mut v = 0;
while b > 0 {
let t = a / b;
a -= t * b;
(a, b) = (b, a);
if u < t * v {
u += m - (t * v) % m;
if u >= m {
u -= m;
}
} else {
u -= t * v;
}
(u, v) = (v, u);
}
Some(u)
}
}
pub mod log {
use crate::math::{
gcd_lcm::GcdLcm,
mod_ops::{inv::*, pow::*},
};
use std::collections::HashMap;
pub fn mod_log(a: u64, mut b: u64, mut m: u64) -> Option<u64> {
assert!(
0 < m && m <= 0xFFFFFFFF,
"Violated 0 < m <= 0xFFFFFFFF (m = {m})"
);
if b >= m {
b %= m;
}
if b == 1 {
return Some(0);
}
let mut d = 0;
loop {
let g = a.gcd(m);
if g != 1 {
if b % g != 0 {
return None;
}
d += 1;
m /= g;
b /= g;
b *= mod_inv(a / g, m).unwrap();
b %= m;
if b == 1 {
return Some(d);
}
} else {
break;
}
}
let sq = (m as f64).sqrt() as u64 + 1;
let mut mp = HashMap::new();
let mut t = 1 % m;
for i in 0..sq {
mp.entry(t).or_insert(i);
t *= a;
t %= m;
}
let x = mod_pow(mod_inv(a, m).unwrap(), sq, m);
let mut t = b % m;
for i in 0..sq {
if let Some(k) = mp.get(&t) {
return Some(i * sq + k + d);
}
t *= x;
t %= m;
}
None
}
}
pub mod pow {
#[inline]
pub const fn mod_pow(mut x: u64, mut p: u64, m: u64) -> u64 {
assert!(0 < m && m <= 0xFFFFFFFF, "Violated 0 < m <= 0xFFFFFFFF");
if x >= m {
x %= m;
}
let mut ret = 1;
while p > 0 {
if (p & 1) != 0 {
ret = (ret * x) % m;
}
x = (x * x) % m;
p >>= 1;
}
ret
}
}
pub mod root {
use crate::math::{
gcd_lcm::GcdLcm,
mod_ops::{inv::mod_inv, log::mod_log, pow::mod_pow},
primitive_root_u64::primitive_root_u64,
};
pub fn mod_kth_root(a: u64, k: u64, p: u64) -> Option<u64> {
let g = primitive_root_u64(p);
let y = mod_log(g, a, p)?;
let yg = y.gcd(p - 1);
let kg = k.gcd(p - 1);
if !yg.is_multiple_of(kg) {
return None;
}
let k_ = k / kg;
let y_ = y / kg;
let p_ = (p - 1) / kg;
let z = y_ * mod_inv(k_, p_).unwrap() % p_;
let x = mod_pow(g, z, p);
assert_eq!(mod_pow(x, k, p), a % p);
Some(x)
}
}
}
pub mod primality {
pub mod miller_rabin {
use crate::math::montgomery::*;
pub use crate::math::primality::PrimalityTest;
fn is_composite(a: u64, s: u32, d: u64, mg: Montgomery) -> bool {
let a = mg.wrap(a);
let pp = mg.wrap(mg.modulo() - 1);
let mut x = mg.pow(a, d);
if mg.unwrap(x) == 1 {
false
} else {
for _ in 0..s {
if x == pp {
return false;
}
x = mg.mul(x, x);
}
true
}
}
pub struct MillerRabin;
impl PrimalityTest<u64> for MillerRabin {
fn is_prime(&self, n: u64) -> bool {
if n <= 1 {
false
} else if n == 2 {
true
} else if n % 2 == 0 {
false
} else {
let s = (n - 1).trailing_zeros();
let d = (n - 1) >> s;
let mg = Montgomery::new(n);
if n < 4_759_123_141 {
![2, 7, 61]
.into_iter()
.any(|a| a < n && is_composite(a, s, d, mg))
} else {
![2, 325, 9375, 28178, 450775, 9780504, 1795265022]
.into_iter()
.any(|a| a < n && is_composite(a, s, d, mg))
}
}
}
}
}
pub trait PrimalityTest<T> {
fn is_prime(&self, value: T) -> bool;
}
}
pub mod primitive_root_u64 {
use crate::math::{factorize::pollard_rho::*, montgomery::*, primality::miller_rabin::*};
pub fn primitive_root_u64(p: u64) -> u64 {
if p == 2 {
return 1;
}
assert!(MillerRabin.is_prime(p), "{p} is not a prime number.");
let pf = pollard_rho(p - 1);
let mn = Montgomery::new(p);
(2..p)
.find(|&g| {
pf.iter()
.all(|f| mn.unwrap(mn.pow(mn.wrap(g), (p - 1) / f)) != 1)
})
.expect("No primitive roots.")
}
}
pub mod montgomery {
const B: u32 = 64;
const R: u128 = 1 << B;
const MASK: u128 = R - 1;
#[derive(Clone, Copy)]
pub struct Montgomery {
modulo: u64,
r2: u128,
m: u64,
}
#[derive(Clone, Copy, PartialEq)]
pub struct Wrapped(pub u64);
impl Montgomery {
pub fn new(modulo: u64) -> Self {
assert!(modulo % 2 != 0);
assert!(modulo > 0);
let r = R % modulo as u128;
let r2 = r * r % modulo as u128;
let m = {
let mut ret: u64 = 0;
let mut r = R;
let mut i = 1;
let mut t = 0;
while r > 1 {
if t % 2 == 0 {
t += modulo;
ret += i;
}
t >>= 1;
r >>= 1;
i <<= 1;
}
ret
};
Self { modulo, r2, m }
}
pub fn modulo(&self) -> u64 {
self.modulo
}
fn reduce(&self, value: u128) -> u64 {
let &Self { modulo, m, .. } = self;
let mut ret =
(((((value & MASK) * m as u128) & MASK) * modulo as u128 + value) >> B) as u64;
if ret >= modulo {
ret -= modulo;
}
ret
}
pub fn wrap(&self, a: u64) -> Wrapped {
Wrapped(self.reduce(a as u128 * self.r2))
}
pub fn unwrap(&self, a: Wrapped) -> u64 {
self.reduce(a.0 as u128)
}
pub fn mul(&self, a: Wrapped, b: Wrapped) -> Wrapped {
Wrapped(self.reduce(a.0 as u128 * b.0 as u128))
}
pub fn add(&self, a: Wrapped, b: Wrapped) -> Wrapped {
let mut t = a.0 as u128 + b.0 as u128;
if t > self.modulo as u128 {
t -= self.modulo as u128;
}
Wrapped(t as u64)
}
pub fn sub(&self, a: Wrapped, b: Wrapped) -> Wrapped {
let mut t = a.0 as u128;
if t < b.0 as u128 {
t += self.modulo as u128;
}
t -= b.0 as u128;
Wrapped(t as u64)
}
pub fn pow(&self, mut a: Wrapped, mut p: u64) -> Wrapped {
let mut ret = self.wrap(1);
while p > 0 {
if (p & 1) != 0 {
ret = self.mul(ret, a);
}
a = self.mul(a, a);
p >>= 1;
}
ret
}
}
}
}