結果
| 問題 |
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()
}
}