#1049294 (Rust) No.2751 429-like Number

• 問題: No.2751 429-like Number
• ユーザー: るこーそー
• 提出日時: 2025-03-04 20:59:54
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 562 ms / 4,000 ms
• コード長: 12,046 bytes
• コンパイル時間: 11,784 ms
• コンパイル使用メモリ: 389,328 KB
• 実行使用メモリ: 8,608 KB
• 最終ジャッジ日時: 2025-03-04 21:00:27
• 合計ジャッジ時間: 17,451 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 6
other	AC * 22

コンパイルメッセージ

warning: struct `UnionFind` is never constructed
   --> src/main.rs:297:8
    |
297 | struct UnionFind {
    |        ^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: associated items `new`, `root`, `merge`, `same`, and `groups` are never used
   --> src/main.rs:302:8
    |
301 | impl UnionFind {
    | -------------- associated items in this implementation
302 |     fn new(n: usize) -> Self {
    |        ^^^
...
308 |     fn root(&mut self, x: usize) -> usize {
    |        ^^^^
...
317 |     fn merge(&mut self, x: usize, y: usize) -> usize {
    |        ^^^^^
...
331 |     fn same(&mut self, x: usize, y: usize) -> bool {
    |        ^^^^
...
335 |     fn groups(&mut self) -> Vec<Vec<usize>> {
    |        ^^^^^^

warning: struct `SegTree` is never constructed
   --> src/main.rs:343:8
    |
343 | struct SegTree<S, Op, E> {
    |        ^^^^^^^

warning: associated items `new`, `from_vec`, `set`, `get`, `prod`, and `all_prod` are never used
   --> src/main.rs:350:8
    |
349 | impl<S: Clone, Op: Fn(S, S) -> S, E: Fn() -> S> SegTree<S, Op, E> {
    | ----------------------------------------------------------------- associated items in this implementation
350 |     fn new(op: Op, e: E, n: usize) -> Self {
    |        ^^^
...
359 |     fn from_vec(op: Op, e: E, v: Vec<S>) -> Self {
    |        ^^^^^^^^
...
374 |     fn set(&mut self, index: usize, x: S) {
    |        ^^^
...
383 |     fn get(&self, index: usize) -> S {
    |        ^^^
...
387 |     fn prod(&self, l: usize, r: usize) -> S {
    |        ^^^^
...
408 |     fn all_prod(&self) -> S {
    |        ^^^^^^^^

warning: function `lcm` is never used
  --> src/main.rs:31:12
   |
31 |     pub fn lcm<T>(a: T, b: T) -> T where T: UInteger {
   |            ^^^

warning: function `pow` is never used
  --> src/main.rs:60:12
   |
60 |     pub fn pow<T,U>(base: T, exp: U) -> T 
   |            ^^^

warning: function `lpf` is never used
  --> src/main.rs:83:12
   |
83 |     pub fn lpf(n: usi

ソースコード

fn getline() -> String{
    let mut __ret=String::new();
    std::io::stdin().read_line(&mut __ret).unwrap();
    return __ret;
}
fn main() {
    let t=getline();
    let q:usize=t.trim().parse().unwrap();
    for _ in 0..q{
        let t=getline();
        let p:usize=t.trim().parse().unwrap();
        let prime=mathutils::pollard_rho_factorize(p);
        println!("{}",if prime.len()==3{"Yes"}else{"No"});
    }
}

mod mathutils{
    pub trait Integer : Copy + PartialEq + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self> + std::ops::Rem<Output = Self> + std::ops::Mul<Output = Self> + std::ops::Div<Output = Self> + From<u8> + std::ops::BitAnd<Output = Self> + std::ops::ShrAssign + std::ops::Neg<Output = Self> + std::cmp::PartialOrd{}
    impl<T> Integer for T where T: Copy + PartialEq + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self> + std::ops::Rem<Output = T> + std::ops::Mul<Output = T> + std::ops::Div<Output = T> + From<u8> + std::ops::BitAnd<Output = T> + std::ops::ShrAssign + std::ops::Neg<Output = T> + std::cmp::PartialOrd {}
    pub trait UInteger : Copy + PartialEq + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self> + std::ops::Rem<Output = Self> + std::ops::Mul<Output = Self> + std::ops::Div<Output = Self> + From<u8> + std::ops::BitAnd<Output = Self> + std::ops::ShrAssign + std::cmp::PartialOrd + std::ops::Shl<Output = Self>{}
    impl<T> UInteger for T where T: Copy + PartialEq + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self> + std::ops::Rem<Output = T> + std::ops::Mul<Output = T> + std::ops::Div<Output = T> + From<u8> + std::ops::BitAnd<Output = T> + std::ops::ShrAssign + std::cmp::PartialOrd + std::ops::Shl<Output = Self>{}
    
    pub fn gcd<T>(a: T, b: T) -> T where T: UInteger {
        let (mut a, mut b) = (a, b);
        while b != T::from(0) {
            (a, b) = (b, a % b);
        }
        a
    }

    pub fn lcm<T>(a: T, b: T) -> T where T: UInteger {
        a / gcd(a, b) * b
    }

    pub fn extgcd<T>(a: T, b: T) -> (T, T, T) where T: UInteger {
        if b == T::from(0) {
            return (a, T::from(1), T::from(0));
        }
        let (d, x, y) = extgcd(b, a % b);
        (d, y, x - a / b * y)
    }

    pub fn powmod<T,U>(base: T, exp: U, modulo: T) -> T 
    where T: UInteger, U: Integer,
    {
        if exp < U::from(0) {
            return powmod(invmod(base, modulo), -exp, modulo);
        }
        let (mut base, mut exp, mut res) = (base, exp, T::from(1));
        while exp!=U::from(0) {
            if exp&U::from(1) == U::from(1) {
                res = (res * base) % modulo;
            }
            exp >>= U::from(1);
            base = (base * base) % modulo;
        }
        res
    }

    pub fn pow<T,U>(base: T, exp: U) -> T 
    where T: UInteger, U: Integer 
    {
        let (mut base, mut exp, mut res) = (base, exp, T::from(1));
        while exp != U::from(0) {
            if exp&U::from(1) == U::from(1) {
                res = res * base;
            }
            exp >>= U::from(1);
            if exp == U::from(0){
                break;
            }
            base = base * base;
        }
        res
    }

    pub fn invmod<T>(x: T, modulo: T) -> T where T: UInteger {
        let (d, x, _) = extgcd(x, modulo);
        assert!(d==T::from(1));
        (x + modulo) % modulo
    }

    pub fn lpf(n: usize) -> Vec<usize> {
        let mut prime = vec![];
        let mut lpf = vec![1; n + 1];
        for d in 2..=n {
            if lpf[d] == 1 {
                lpf[d] = d;
                prime.push(d);
            }
            for &p in &prime {
                if p*d > n || p > lpf[d] {
                    break;
                }
                lpf[p*d] = p;
            }
        }
        lpf
    }
    
    pub fn lpf_factorize(n: usize, lpf: &Vec<usize>) -> Vec<(usize, usize)> {
        let mut prime = vec![];
        let mut n = n;
        while n > 1{
            let mut exp = 0;
            let p = lpf[n];
            while n % p == 0 {
                n /= p;
                exp += 1;
            }
            prime.push((p, exp));
        }
        prime
    }

    pub fn lpf_divisors(n: usize, lpf: &Vec<usize>) -> Vec<usize> {
        let prime = self::lpf_factorize(n, &lpf);
        let mut divisors = vec![1];
        for i in 0..prime.len() {
            let mut new_divisors = vec![];
            for &d in &divisors {
                let mut mul = 1;
                for _ in 0..=prime[i].1 {
                    new_divisors.push(d * mul);
                    mul *= prime[i].0;
                }
            }
            divisors = new_divisors;
        }
        divisors
    }

    pub fn factorize(n: usize) -> Vec<(usize, usize)> {
        let mut prime = vec![];
        let (mut n, mut d) = (n, 2);
        while d*d <= n {
            let mut exp = 0;
            while n % d == 0 {
                n /= d;
                exp += 1;
            }
            if exp > 1 {
                prime.push((d, exp));
            }
            d += 1;
        }
        if n > 1 {
            prime.push((n, 1));
        }
        prime
    }

    pub fn divisors(n: usize) -> Vec<usize> {
        let mut divisors = vec![];
        let mut d = 1;
        while d*d <= n {
            if n % d == 0 {
                divisors.push(d);
                if d*d != n {
                    divisors.push(n / d);
                }
            }
            d += 1;
        }
        divisors
    }

    pub fn is_prime(n: usize) -> bool {
        if n < 2 {
            return false;
        }
        let mut d = 2;
        while d*d <= n {
            if n % d == 0 {
                return false;
            }
            d += 1;
        }
        true
    }

    pub struct Xorshift64 {
        a: u64,
    }
    pub fn xorshift64(state: &mut Xorshift64) -> u64 {
        let mut x: u64 = state.a;
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        state.a = x;
        x
    }
    
    pub fn miller_rabin(n: usize) -> bool {
        let n = n as u128;
        let test_number: [u128; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];
        if n == 2 {
            return true;
        }
        if n == 1 || n & 1 == 0 {
            return false;
        } 
        let mut d = n - 1;
        while d & 1 == 0 {
            d >>= 1;
        }
        for &a in &test_number {
            let a = (a % (n - 1)) + 1;
            let mut t = d;
            let mut y = powmod(a, t as i128, n);
            while t != n - 1 && y != 1 && y != n - 1 {
                y = (y * y) % n;
                t <<= 1;
            }
            if y != n - 1 && t & 1 == 0 {
                return false;
            }
        }
        true
    }

    pub fn pollard_rho(n: usize) -> usize {
        let n = n as u128;
        if n & 1 == 0 {
            return 2_usize;
        }
        if miller_rabin(n as usize) {
            return n as usize;
        }
        let mut state = self::Xorshift64 { a: n as u64 };
        let mut step: u128 = 0;
        loop {
            step=(step + self::xorshift64(&mut state) as u128 % n ) % n;
            let (mut x, mut y) = (step, (self::powmod(step, 2, n) + step) % n);
            loop {
                let p = self::gcd(if y >= x {y - x} else {x - y} + n, n);
                if p == 0 || p == n {
                    break;
                }
                if p != 1 {
                    return p as usize;
                }
                x = (self::powmod(x, 2, n) + step) % n;
                y = (self::powmod(self::powmod(y, 2, n) + step, 2, n) + step) % n;
            }
        }
    }

    pub fn pollard_rho_factorize(n: usize) -> Vec<usize> {
        if n == 1 {
            return vec![];
        }
        if miller_rabin(n) {
            return vec![n];
        }
        let d = pollard_rho(n);
        let mut res = pollard_rho_factorize(d);
        res.append(&mut pollard_rho_factorize(n / d));
        res
    }
    pub struct Combination {
        fact: Vec<usize>,
        inv_fact: Vec<usize>,
        modulo: Option<usize>,
    }
    impl Combination {
        pub fn new(n: usize, modulo: Option<usize>) -> Self {
            let mut fact = vec![1; n + 1];
            let mut inv_fact = vec![1; n + 1];
            if let Some(m) = modulo {
                for i in 1..=n {
                    fact[i] = fact[i - 1] * i % m;
                }
                inv_fact[n] = self::powmod(fact[n] as i64, -1_i64, m as i64) as usize;
                for i in (1..=n).rev() {
                    inv_fact[i - 1] = inv_fact[i] * i % m;
                }
            } else {
                for i in 1..=n {
                    fact[i] = fact[i - 1] * i;
                }
            }
            Self { fact, inv_fact, modulo }
        }
        pub fn comb(&self, n: usize, k: usize) -> usize {
            if n < k {
                return 0;
            }
            if let Some(m) = self.modulo {
                self.fact[n] * self.inv_fact[k] % m * self.inv_fact[n - k] % m
            } else {
                self.fact[n] / self.fact[k] / self.fact[n - k]
            }
        }
    }
}
struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}
impl UnionFind {
    fn new(n: usize) -> Self {
        let parent = (0..n).collect();
        let rank = vec![1; n];
        Self { parent, rank }
    }

    fn root(&mut self, x: usize) -> usize {
        if self.parent[x] == x {
            x
        } else {
            self.parent[x] = self.root(self.parent[x]);
            self.parent[x]
        }
    }
    
    fn merge(&mut self, x: usize, y: usize) -> usize {
        let mut x = self.root(x);
        let mut y = self.root(y);
        if x == y {
            return x;
        }
        if self.rank[x] < self.rank[y] {
            (x, y) = (y, x);
        }
        self.rank[x] += self.rank[y];
        self.parent[y] = x;
        x
    }

    fn same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    fn groups(&mut self) -> Vec<Vec<usize>> {
        let mut group = vec![vec![]; self.parent.len()];
        for i in 0..self.parent.len() {
            group[self.root(i)].push(i);
        }
        group.into_iter().filter(|x| !x.is_empty()).collect()
    }
}
struct SegTree<S, Op, E> {
    size: usize,
    d: Vec<S>,
    op: Op,
    e: E,
}
impl<S: Clone, Op: Fn(S, S) -> S, E: Fn() -> S> SegTree<S, Op, E> {
    fn new(op: Op, e: E, n: usize) -> Self {
        let mut size = 1;
        while size < n {
            size <<= 1;
        }
        let d = vec![e(); size << 1];
        Self { size, d, op, e }
    }

    fn from_vec(op: Op, e: E, v: Vec<S>) -> Self {
        let mut size = 1;
        while size < v.len() {
            size <<= 1;
        }
        let mut d = vec![e(); size << 1];
        for i in 0..v.len() {
            d[size + i] = v[i].clone();
        }
        for i in (1..size).rev() {
            d[i] = (op)(d[i << 1].clone(), d[(i << 1) | 1].clone());
        }
        Self { size, d, op, e }
    }

    fn set(&mut self, index: usize, x: S) {
        let mut i = index + self.size;
        self.d[i] = x;
        while i > 1 {
            i >>= 1;
            self.d[i] = (self.op)(self.d[i << 1].clone(), self.d[(i << 1) | 1].clone());
        }
    }

    fn get(&self, index: usize) -> S {
        self.d[index + self.size].clone()
    }

    fn prod(&self, l: usize, r: usize) -> S {
        let mut sml = (self.e)();
        let mut smr = (self.e)();
        let mut l = l + self.size;
        let mut r = r + self.size;

        while l < r {
            if l & 1 == 1 {
                sml = (self.op)(sml, self.d[l].clone());
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                smr = (self.op)(self.d[r].clone(), smr);
            }
            l >>= 1;
            r >>= 1;
        }
        (self.op)(sml, smr)
    }

    fn all_prod(&self) -> S {
        self.d[1].clone()
    }
}