結果

問題 No.1287 えぬけー
コンテスト
ユーザー Strorkis
提出日時 2020-11-14 00:13:28
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 2,636 bytes
コンパイル時間 14,604 ms
コンパイル使用メモリ 394,688 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-22 22:25:46
合計ジャッジ時間 15,888 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{BufRead, BufReader, BufWriter, Write};
use std::{str::FromStr, iter::FromIterator, fmt::Display};

pub struct ProconIo<'a> {
    pub reader: BufReader<std::io::StdinLock<'a>>,
    pub writer: BufWriter<std::io::StdoutLock<'a>>,
}

impl ProconIo<'_> {
    pub fn get_input(&mut self) -> String {
        let mut input = String::new();
        self.reader.read_line(&mut input).ok();
        input
    }

    pub fn read<T: FromStr>(&mut self) -> T {
        self.get_input().trim().parse().ok().unwrap()
    }

    pub fn read_col<T: FromStr, C: FromIterator<T>>(&mut self) -> C {
        self.get_input()
            .split_whitespace()
            .map(|x| x.parse().ok().unwrap())
            .collect()
    }

    pub fn read_chars<C: FromIterator<char>>(&mut self) -> C {
        self.get_input().trim().chars().collect()
    }

    pub fn writeln<T: Display>(&mut self, x: T) {
        writeln!(self.writer, "{}", x).ok();
    }

    pub fn writeln_col<C: IntoIterator>(&mut self, c: C)
    where
        C::Item: Display,
    {
        self.writeln(
            c.into_iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        )
    }
}

#[allow(unused_macros)]
macro_rules! read_tuple {
    ( $io:expr, $( $t:ty ),* ) => {{
        let input = $io.get_input();
        let mut iter = input.split_whitespace();
        ( $( iter.next().unwrap().parse::<$t>().unwrap() ),* )
    }};
}

use std::mem::swap;

fn safe_mod(mut x: i64, m: i64) -> i64 {
    x %= m;
    if x < 0 { x + m } else { x }
}

fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
    let a = safe_mod(a, b);
    if a == 0 { return (b, 0); }

    let (mut s, mut t) = (b, a);
    let (mut m0, mut m1) = (0, 1);

    while t != 0 {
        let u = s / t;
        s -= t * u;
        m0 -= m1 * u;

        swap(&mut s, &mut t);
        swap(&mut m0, &mut m1);
    }

    (s, if m0 < 0 { m0 + b / s } else { m0 })
}

fn solve(io: &mut ProconIo) {
    const MOD: i64 = 1_000_000_007;

    let (x, k) = read_tuple!(io, i64, i64);

    let pow = |mut a: i64, mut n: i64| -> i64 {
        let mut res = 1;
        while n > 0 {
            if n & 1 > 0 {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            n >>= 1;
        }
        res
    };

    io.writeln(pow(x, inv_gcd(k, MOD - 1).1));
}

fn main() {
    let stdin = std::io::stdin();
    let stdout = std::io::stdout();
    let mut io = ProconIo {
        reader: BufReader::new(stdin.lock()),
        writer: BufWriter::new(stdout.lock()),
    };
    for _ in 0..io.read::<usize>() { solve(&mut io); }
}
0