結果
| 問題 |
No.2682 Visible Divisible
|
| コンテスト | |
| ユーザー |
 Moss_Local
|
| 提出日時 | 2024-03-20 22:05:41 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 62 ms / 2,000 ms |
| コード長 | 11,023 bytes |
| コンパイル時間 | 14,311 ms |
| コンパイル使用メモリ | 398,896 KB |
| 実行使用メモリ | 10,180 KB |
| 最終ジャッジ日時 | 2024-09-30 07:56:45 |
| 合計ジャッジ時間 | 16,021 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 |
コンパイルメッセージ
warning: variable does not need to be mutable
--> src/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
--> src/main.rs:128:9
|
128 | let mut vec: Vec<i64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:133:9
|
133 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:139:9
|
139 | let mut vec: Vec<f64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:144:9
|
144 | let mut vec: Vec<char> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:149:9
|
149 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:154:9
|
154 | let mut vec: Vec<i64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:160:9
|
160 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/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
ソースコード
// -*- 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;
}