#962621 (Rust) No.2682 Visible Divisible

• 問題: No.2682 Visible Divisible
• ユーザー: Moss_Local
• 提出日時: 2024-03-20 22:05:41
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 67 ms / 2,000 ms
• コード長: 11,023 bytes
• コンパイル時間: 2,486 ms
• コンパイル使用メモリ: 203,520 KB
• 実行使用メモリ: 10,108 KB
• 最終ジャッジ日時: 2024-03-20 22:05:46
• 合計ジャッジ時間: 4,398 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	43 ms; 9,676 KB
testcase_01	AC	67 ms; 9,756 KB
testcase_02	AC	67 ms; 9,804 KB
testcase_03	AC	62 ms; 9,836 KB
testcase_04	AC	31 ms; 9,524 KB
testcase_05	AC	32 ms; 9,532 KB
testcase_06	AC	32 ms; 9,700 KB
testcase_07	AC	32 ms; 9,472 KB
testcase_08	AC	1 ms; 6,676 KB
testcase_09	AC	1 ms; 6,676 KB
testcase_10	AC	1 ms; 6,676 KB
testcase_11	AC	41 ms; 9,792 KB
testcase_12	AC	37 ms; 10,108 KB
testcase_13	AC	32 ms; 9,600 KB
testcase_14	AC	63 ms; 9,708 KB
testcase_15	AC	51 ms; 9,600 KB
testcase_16	AC	40 ms; 9,636 KB

コンパイルメッセージ

warning: variable does not need to be mutable
   --> Main.rs:122:9
    |
122 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> Main.rs:128:9
    |
128 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:133:9
    |
133 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:139:9
    |
139 |     let mut vec: Vec<f64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:144:9
    |
144 |     let mut vec: Vec<char> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:149:9
    |
149 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:154:9
    |
154 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:160:9
    |
160 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:73:17
    |
73  |             let mut map = ::std::collections::BTreeMap::new();
    |                 ----^^^
    |                 |
    |                 help: remove this `mut`
...
434 |     let mut pf = map![];
    |                  ------ in this macro invocation
    |
    = note: this warning originat

ソースコード

// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
// use core::num;
use std::cmp::*;
use std::fmt::*;
use std::hash::*;
use std::iter::FromIterator;
use std::*;
use std::{cmp, collections, fmt, io, iter, ops, str};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD1: i64 = 1000000007;
const MOD9: i64 = 998244353;
const MOD: i64 = MOD9;
// const MOD: i64 = MOD2;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;

// use proconio::input;
// const MOD: i64 = INF;

use cmp::Ordering::*;
use std::collections::*;

use std::io::stdin;
use std::io::stdout;
use std::io::Write;

macro_rules! p {
    ($x:expr) => {
        //if expr
        println!("{}", $x);
    };
}

macro_rules! vp {
    // vector print separate with space
    ($x:expr) => {
        println!(
            "{}",
            $x.iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        );
    };
}

macro_rules! d {
    ($x:expr) => {
        eprintln!("{:?}", $x);
    };
}
macro_rules! yn {
    ($val:expr) => {
        if $val {
            println!("Yes");
        } else {
            println!("No");
        }
    };
}

macro_rules! map{
    // declear btreemap
    ($($key:expr => $val:expr),*) => {
        {
            let mut map = ::std::collections::BTreeMap::new();
            $(
                map.insert($key, $val);
            )*
            map
        }
    };
}

macro_rules! set{
    // declear btreemap
    ($($key:expr),*) => {
        {
            let mut set = ::std::collections::BTreeSet::new();
            $(
                set.insert($key);
            )*
            set
        }
    };
}

fn main() {
    solve();
}

// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

#[allow(dead_code)]
fn readii() -> (i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readff() -> (f64, f64) {
    let mut vec: Vec<f64> = read_vec();
    (vec[0], vec[1])
}

fn readcc() -> (char, char) {
    let mut vec: Vec<char> = read_vec();
    (vec[0], vec[1])
}

fn readuuu() -> (usize, usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2], vec[3])
}

#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1], vec[2], vec[3])
}

fn read_imat(h: usize) -> Vec<Vec<i64>> {
    (0..h).map(|_| read_vec()).collect()
}
fn read_cmat(h: usize) -> Vec<Vec<char>> {
    (0..h).map(|_| read::<String>().chars().collect()).collect()
}

fn prime_factorization(x: usize) -> BTreeMap<usize, usize> {
    let mut res: BTreeMap<usize, usize> = BTreeMap::new();
    let mut xx = x;
    let mut p: usize = 2;
    while p * p <= xx {
        while xx % p == 0 {
            // println!("{:?}", p);
            let t = res.get_mut(&p);
            if t.is_none() {
                res.insert(p, 1);
            } else {
                *t.unwrap() += 1;
            }
            xx /= p;
        }
        // println!("{:?} {:?}", p, res);
        p += 1;
    }

    if xx != 1 {
        let t = res.get_mut(&xx);
        if t.is_none() {
            res.insert(xx, 1);
        } else {
            *t.unwrap() += 1;
        }
    }
    res
}

pub struct Montgomery {
    m: usize,
    pow_r: usize,
    mp: usize,
    mask: usize,
    r2: usize,
}

impl Montgomery {
    pub fn new(m: usize, pow_r: usize) -> Self {
        fn extended_gcd(a: i128, b: i128) -> (i128, i128) {
            if (a, b) == (1, 0) {
                (1, 0)
            } else {
                let (x, y) = extended_gcd(b, a % b);
                (y, x - (a / b) * y)
            }
        }
        let mp = {
            let (_, b) = extended_gcd(1i128 << pow_r, m as i128);
            if b <= 0 {
                (-b) as usize
            } else {
                (-b + (1 << pow_r)) as usize
            }
        };
        let mask = std::usize::MAX;
        let r2 =
            (((1u128 << pow_r) % m as u128) * ((1u128 << pow_r) % m as u128) % m as u128) as usize;
        Montgomery {
            m,
            pow_r,
            mp,
            mask,
            r2,
        }
    }

    /// - Returns:
    ///     - t * R^{-1} mod N
    fn mr(&self, t: u128) -> usize {
        let temp = {
            let mask = self.mask as u128;
            let mp = self.mp as u128;
            let m = self.m as u128;
            let pow_r = self.pow_r as u128;
            ((t + ((t & mask) * mp & mask) * m) >> pow_r) as usize
        };

        if temp >= self.m {
            temp - self.m
        } else {
            temp
        }
    }

    /// - Returns:
    ///     - a + b mod N
    pub fn add(&self, a: usize, b: usize) -> usize {
        (a + b) % self.m
    }

    /// - Returns:
    ///     - a * b mod N
    pub fn mul(&self, a: usize, b: usize) -> usize {
        self.mr(self.mr(a as u128 * b as u128) as u128 * self.r2 as u128)
    }
}

/// - Returns:
///     - GCD(a, b)
pub fn gcd(mut a: usize, mut b: usize) -> usize {
    if a < b {
        std::mem::swap(&mut a, &mut b);
    }
    while b != 0 {
        let temp = a % b;
        a = b;
        b = temp;
    }
    a
}

/// - Returns:
///     - if n is prime number:  
///         * true  
///     - else:  
///         * false  
///
/// - Note:
///     - Algorithm:
///         - Miller-Rabin
pub fn is_prime_large(n: usize) -> bool {
    if n == 0 || n == 1 || (n > 2 && n % 2 == 0) {
        return false;
    }

    if n == 2 {
        return true;
    }

    /// - Returns:
    ///     - $a^{n}$ modulo $m$
    pub fn mod_pow(a: usize, mut n: usize, mont: &Montgomery) -> usize {
        let mut res = 1;
        let mut x = a;
        while n > 0 {
            if n % 2 == 1 {
                res = mont.mul(res, x);
            }
            x = mont.mul(x, x);
            n /= 2;
        }

        res
    }

    let s = (n - 1).trailing_zeros();
    let d = (n - 1) / (1 << s);
    let mont = Montgomery::new(n, 64);

    let f = |mut a| {
        a %= n;
        if a == 0 {
            return true;
        }
        let mut ad = mod_pow(a, d, &mont);
        if ad == 1 || ad == n - 1 {
            return true;
        }

        for _ in 0..s {
            ad = mont.mul(ad, ad);
            if ad == n - 1 {
                return true;
            }
        }

        false
    };

    const A: [usize; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];
    A.iter().all(|x| f(*x))
}

pub fn factorize_sub(n: usize, res: &mut Vec<usize>) {
    if n == 1 {
        return;
    }

    if is_prime_large(n) {
        res.push(n);
        return;
    }

    let n2 = (n as f64).powf(1.0 / 8.0) as usize;

    // find divisor of n
    let d = if n % 2 == 0 {
        2
    } else {
        (|| {
            let mont = Montgomery::new(n, 64);
            for c in 1234567891.. {
                let f = |a, mont: &Montgomery| mont.add(mont.mul(a, a), c);

                let mut a = vec![2, f(2, &mont)];
                let mut i1 = 0;
                let mut i2 = 1;
                loop {
                    let mut q = 1;
                    for _ in 0..n2 {
                        a.push(f(a[i2], &mont));
                        a.push(f(a[i2 + 1], &mont));
                        i1 += 1;
                        i2 += 2;
                        q = mont.mul(q, std::cmp::max(a[i1], a[i2]) - std::cmp::min(a[i1], a[i2]));
                    }
                    let g = gcd(q, n);
                    if 1 < g && g < n {
                        return g;
                    }
                    if g == n {
                        break;
                    }
                    a.push(f(a[i2], &mont));
                    a.push(f(a[i2 + 1], &mont));
                    i1 += 1;
                    i2 += 2;
                }

                let mut a = vec![2, f(2, &mont)];
                let mut i1 = 0;
                let mut i2 = 1;
                loop {
                    let g = gcd(std::cmp::max(a[i1], a[i2]) - std::cmp::min(a[i1], a[i2]), n);
                    if 1 < g && g < n {
                        return g;
                    }
                    if g == n {
                        break;
                    }
                    a.push(f(a[i2], &mont));
                    a.push(f(a[i2 + 1], &mont));
                    i1 += 1;
                    i2 += 2;
                }
            }
            unreachable!()
        })()
    };

    factorize_sub(d, res);
    factorize_sub(n / d, res);
}

/// - Returns:
///     - result of integer factorization of n
/// - Note:
///     - Algorithm:
///         - Pollard's rho algorithm
pub fn factorize(n: usize) -> Vec<usize> {
    assert!(n != 0);
    let mut res = vec![];

    factorize_sub(n, &mut res);

    res.sort();
    res
}
fn solve() {
    let (n, k) = readuu();
    let factors = factorize(k);
    let mut pf = map![];
    for f in factors {
        let t = pf.get(&f);
        if t.is_none() {
            pf.insert(f, 1);
        } else {
            pf.insert(f, t.unwrap() + 1);
        }
    }
    let mut max_divise_num = map![];
    let mut vec: Vec<usize> = read_vec();
    // let primes = pf.keys().collect::<Vec<_>>();
    let mut primes: Vec<usize> = vec![];
    for (k, _) in &pf {
        primes.push(*k);
    }
    for i in 0..n {
        let mut x = vec[i];
        for p in &primes {
            let mut cnt = 0;
            while x % p == 0 {
                x /= p;
                cnt += 1;
            }
            let t = max_divise_num.get_mut(p).copied();
            if t.is_none() {
                max_divise_num.insert(*p, cnt);
            } else {
                max_divise_num.insert(*p, max(cnt, t.unwrap()));
            }
        }
    }
    let mut can_divise = true;
    for (k, v) in &pf {
        let num = max_divise_num.get(k).copied().unwrap_or(0);
        if num < *v {
            can_divise = false;
            break;
        }
    }
    yn!(can_divise);
    return;
}