結果

問題 No.3115 One Power One Kill
ユーザー かえる☔
提出日時 2025-04-20 17:42:04
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 5,800 bytes
コンパイル時間 14,024 ms
コンパイル使用メモリ 387,656 KB
実行使用メモリ 26,264 KB
平均クエリ数 2.00
最終ジャッジ日時 2025-04-20 17:42:21
合計ジャッジ時間 15,593 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports, non_snake_case, dead_code, unused_macros)]
use proconio::{input, marker::Usize1 as usize1, marker::Chars as chars};
use std::{collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque as Deque}, default::Default, io::Write, mem::swap};

macro_rules! chmax {
    ($target:expr, $value:expr) => {
        if $target < $value {
            $target = $value;
            true
        } else {false}
    };
}
macro_rules! chmin {
    ($target:expr, $value:expr) => {
        if $target > $value {
            $target = $value;
            true
        } else {false}
    };
}

fn yn(x: bool) {
    if x {
        println!("Yes")
    } else {
        println!("No")
    }
}

fn extend_euclid(a: i64, b: i64) -> Result<(i64, i64), i64> {
    /*
    ax+by=1 を満たすOk((x, y))を返す。存在しなければErr(gcd(a, b))を返す。
     */
    fn inner(a: i64, b: i64, ae: (i64, i64), be: (i64, i64)) -> Result<(i64, i64), i64> {
        if b == 0 {
            if a == 1 {
                return Ok(ae);
            } else {
                return Err(a);
            }
        }
        let mut new_be = (0, 0);
        new_be.0 = ae.0 - a / b * be.0;
        new_be.1 = ae.1 - a / b * be.1;
        inner(b, a%b, be, new_be)
    }
    inner(a, b, (1, 0), (0, 1))
}


#[derive(Debug)]
struct DisjointSetUnion {
    parents: Vec<usize>,
    children: Vec<Vec<usize>>,
    sizes: Vec<usize>,
}
impl DisjointSetUnion {
    fn new(N: usize) -> Self {
        let parents = (0..N).collect();
        let children = vec![vec![]; N];
        let sizes = vec![1; N];
        Self { parents, children, sizes }
    }
    fn root(&self, x: usize) -> usize {
        if self.parents[x] == x {
            x
        } else {
            self.root(self.parents[x])
        }
    }
    fn size(&self, x: usize) -> usize {
        self.sizes[self.root(x)]
    }
    fn union(&mut self, a: usize, b: usize) -> bool {
        let (a, b) = (self.root(a), self.root(b));
        if a==b {
            return false;
        }
        if self.size(a) > self.size(b) {
            self.parents[b] = a;
            self.children[a].push(b);
            self.sizes[a] += self.sizes[b];
            self.sizes[b] = 0;
        } else {
            self.parents[a] = b;
            self.children[b].push(a);
            self.sizes[b] += self.sizes[a];
            self.sizes[a] = 0;
        }
        true
    }
    fn connections(&self) -> Vec<usize> {
        let mut res = Vec::new();
        for i in 0..self.parents.len() {
            if self.root(i) == i {
                res.push(i)
            }
        }
        res
    }
}

struct SegTree<T: Copy> {
    size: usize,
    dat: Vec<T>,
    update_func: Box<dyn Fn(T, T) -> T>,
    identity: T,
}
impl<T: Copy> SegTree<T> {
    fn new(size: usize, update_func: impl Fn(T, T) -> T + 'static, identity: T) -> Self {
        let size = size.next_power_of_two();
        let dat = vec![identity.clone(); size*2-1];
        Self {
            size, dat, update_func: Box::new(update_func), identity,
        }
    }
    fn update(&mut self, mut i: usize, x: T) {
        i += self.size-1;
        self.dat[i] = x;
        while i > 0 {
            i = (i-1)/2;
            self.dat[i] = (self.update_func)(self.dat[i*2+1], self.dat[i*2+2]);
        }
    }
    fn query(&self, a: usize, b: usize) -> T {
        self.query_sub(a, b, 0, 0, self.size)
    }
    fn query_sub(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
        if r <= a || b <= l {
            self.identity
        } else if a <= l && r <= b {
            self.dat[k]
        } else {
            (self.update_func)(self.query_sub(a, b, k*2+1, l, (l+r)/2), self.query_sub(a, b, k*2+2, (l+r)/2, r))
        }
    }
}
impl SegTree<i64> {
    fn new_rminq(size: usize) -> Self {
        Self::new(size, i64::min, std::i64::MAX)
    }
    fn new_rmaxq(size: usize) -> Self {
        Self::new(size, i64::max, std::i64::MIN)
    }
    fn new_rsq(size: usize) -> Self {
        Self::new(size, |a, b| a+b, 0)
    }
}
impl SegTree<usize> {
    fn new_rminq(size: usize) -> Self {
        Self::new(size, usize::min, std::usize::MAX)
    }
    fn new_rmaxq(size: usize) -> Self {
        Self::new(size, usize::max, std::usize::MIN)
    }
    fn new_rsq(size: usize) -> Self {
        Self::new(size, |a, b| a+b, 0)
    }
}


fn around(i: usize, j: usize, H: usize, W: usize) -> Vec<(usize, usize)> {
    let mut res = vec![];

    if i!=0 {
        res.push((i-1, j));
    }
    if j!=0 {
        res.push((i, j-1));
    }
    if i!=H-1 {
        res.push((i+1, j));
    }
    if j!=W-1 {
        res.push((i, j+1))
    }
    res
}
fn to_index(i: usize, j: usize, W: usize) -> usize {
    i*W+j
}



fn lowerchar2code(c: char) -> usize {
    c as usize - 'a' as usize
}



type ModType = i64;
static MOD: ModType = 1000000007;

fn pow(base: ModType, power: ModType) -> ModType {
    if power == 0 {
        1
    } else if power == 1 {
        base % MOD
    } else {
        if power % 2 == 0 {
           pow(base, power/2).pow(2) % MOD
       } else {
           let tmp = pow(base, power/2).pow(2) % MOD;
           tmp * base % MOD
       }
    }
}

fn recip(x: ModType) -> ModType {
    pow(x, MOD-2)
}


fn main() {
    let (a, b) = (100, 132);

    println!("100 132");

    use std::io::{self, stdin, stdout, BufReader, Write};
    use proconio::{input, source::line::LineSource};
    let mut stdin = LineSource::new(BufReader::new(io::stdin()));
    macro_rules! input(($($tt:tt)*) => (proconio::input!(from &mut stdin, $($tt)*)));

    input! {
        K: i64,
    }
    let y = pow(a, b);
    for x in 100..=100_000 {
        if K == extend_euclid(x, y).err().unwrap_or(1) {
            println!("{}", pow(x, a));
            break;
        }
    }
}
0