2021/04/29

なのだが定数倍に死ぬほど厳しいので、前計算できる部分を で計算しておく。
atcoder.jp

全く歯が立たなかった。正六角形ならば勝てることに気付いて渦巻き状に構築しようとしたがハズレ方針だったっぽい。
atcoder.jp

N番目を取得できるsetとしてFenwick treeを使うこともBSTを使うこともできるが、手元にTreapがあったので貼ることにしたところ、今まで顕在化しなかったバグがあり大爆死した。insert/eraseで実装していたが、merge/splitで全部書き直した。
atcoder.jp

Baby-step Giant-step のアルゴリズムと言うらしい。アイディア的には平方分割。どうしても通らないケースが3つあったが、そういったケースはどうせ1だろうということで、TLEしそうになったら1を出力する邪悪解法で通した。
D - あまり

use std::time::Instant;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let x: u64 = sc.read();
    let p: u64 = sc.read();
    let a: u64 = sc.read();
    let b: u64 = sc.read();

    let start = Instant::now();
    for i in 0.. {
        if let Some(x) = baby_step_giant_step(x, i, p) {
            let d = b - a;
            let x = x % p;
            let a = a % p;
            let b = a + d;
            if a <= x && x <= b {
                println!("{}", i);
                return;
            }
        }
        if start.elapsed().as_millis() > 1500 {
            break;
        }
    }
    let mut xa = mod_pow(x, a, p);
    let mut ans = xa;
    for _ in (a + 1)..=b {
        xa = (xa * x) % p;
        ans = ans.min(xa);

        if start.elapsed().as_millis() > 4900 {
            println!("1");
            return;
        }
    }

    println!("{}", ans);
}

fn mod_pow(x: u64, mut e: u64, m: u64) -> u64 {
    let mut result = 1;
    let mut cur = x;
    while e > 0 {
        if e & 1 == 1 {
            result = (result * cur) % m;
        }
        e >>= 1;
        cur = (cur * cur) % m;
    }
    result
}

fn baby_step_giant_step(x: u64, y: u64, m: u64) -> Option<u64> {
    let h = (m as f64).sqrt() as u64 + 1;

    let mut xby = y;
    let mut baby = vec![(0, 0); h as usize];
    for b in 0..h {
        baby[b as usize] = (xby, b);
        xby = (xby * x) % m;
    }
    baby.sort();

    let xh = mod_pow(x, h, m);
    let mut xah = xh;
    for a in 1..=h {
        match baby.binary_search(&(xah + 1, 0)) {
            Ok(i) => {
                if i > 0 && baby[i - 1].0 == xah {
                    return Some(a * h - baby[i - 1].1);
                }
            }
            Err(i) => {
                if i > 0 && baby[i - 1].0 == xah {
                    return Some(a * h - baby[i - 1].1);
                }
            }
        }
        xah = (xah * xh) % m;
    }
    None
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}