結果
| 問題 | No.2379 Burnside's Theorem |
| ユーザー |
👑  Mizar
|
| 提出日時 | 2023-07-14 21:39:48 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| コード長 | 32,673 bytes |
| コンパイル時間 | 4,622 ms |
| コンパイル使用メモリ | 176,280 KB |
| 実行使用メモリ | 4,376 KB |
| 最終ジャッジ日時 | 2023-10-14 11:43:17 |
| 合計ジャッジ時間 | 3,240 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 0 ms
4,372 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 1 ms
4,372 KB |
| testcase_04 | AC | 1 ms
4,372 KB |
| testcase_05 | AC | 1 ms
4,372 KB |
| testcase_06 | AC | 1 ms
4,376 KB |
| testcase_07 | AC | 1 ms
4,372 KB |
| testcase_08 | AC | 1 ms
4,372 KB |
| testcase_09 | AC | 1 ms
4,372 KB |
| testcase_10 | AC | 1 ms
4,376 KB |
| testcase_11 | AC | 1 ms
4,372 KB |
| testcase_12 | AC | 1 ms
4,372 KB |
| testcase_13 | AC | 1 ms
4,372 KB |
| testcase_14 | AC | 1 ms
4,376 KB |
| testcase_15 | AC | 1 ms
4,376 KB |
| testcase_16 | AC | 1 ms
4,376 KB |
| testcase_17 | AC | 0 ms
4,372 KB |
| testcase_18 | AC | 1 ms
4,372 KB |
| testcase_19 | AC | 1 ms
4,372 KB |
| testcase_20 | AC | 1 ms
4,372 KB |
| testcase_21 | AC | 1 ms
4,376 KB |
| testcase_22 | AC | 1 ms
4,372 KB |
| testcase_23 | AC | 1 ms
4,376 KB |
ソースコード
// -*- coding:utf-8-unix -*-
pub use __cargo_equip::prelude::*;
use crate::__cargo_equip::crates::rho::*;
use std::io::prelude::*;
pub fn main() {
let mut input = String::new();
std::io::stdin().read_to_string(&mut input).unwrap();
let mut tokens = input.split_ascii_whitespace();
let n = tokens.next().unwrap().parse::<u64>().unwrap();
let mut v = factorize(n);
v.dedup();
println!("{}", if v.len() <= 2 { "Yes" } else { "No" });
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `mizar-competitive-integer-issq 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::issq`
/// - `mizar-competitive-integer-jacobi 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::jacobi`
/// - `mizar-competitive-integer-modint32dynamic 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::modint32dynamic`
/// - `mizar-competitive-integer-montodd 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::montodd`
/// - `mizar-competitive-integer-sqrt 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::sqrt`
/// - `mizar-competitive-integer-xorshift 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::xorshift`
/// - `mizar-competitive-misc-invariant 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::invariant`
/// - `mizar-competitive-misc-primint 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::primint`
/// - `mizar-competitive-prime-bpsw 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::bpsw`
/// - `mizar-competitive-prime-miller-rabin-fj32-256 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::miller_rabin_fj32_256`
/// - `mizar-competitive-prime-rho 0.0.0 (git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=b57823e#b57823e821f65e3f51ef0a5a843ae94ff2d06354)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::rho`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod issq {use crate::__cargo_equip::preludes::issq::*;use crate::__cargo_equip::crates::sqrt::*;macro_rules!fn_isqrt_n{($sqrt_newton:ident,$sqrt_exact:ident,$issq_newton:ident,$issq_mod32:ident,$issq_mod48:ident,$issq_mod4095:ident,$issq:ident,$x:ty,$w:literal)=>{pub fn$issq_mod32(x:$x)->bool{(0x02030213u32>>((x as u32)&31))&1==1}pub fn$issq_mod48(x:$x)->bool{(0x1202010213u64>>(x%48))&1==1}pub fn$issq_mod4095(x:$x)->bool{const SQTABLE_MOD4095:[u64;64]=[0x2001002010213,0x4200001008028001,0x20000010004,0x80200082010,0x1800008200044029,0x120080000010,0x2200000080410400,0x8100041000200800,0x800004000020100,0x402000400082201,0x9004000040,0x800002000880,0x18002000012000,0x801208,0x26100000804010,0x80000080000002,0x108040040101045,0x20c00004000102,0x400000100c0010,0x1300000040208,0x804000020010000,0x1008402002400080,0x201001000200040,0x4402000000806000,0x10402000000,0x1040008001200801,0x4080000000020400,0x10083080000002,0x8220140000040000,0x800084020100000,0x80010400010000,0x1200020108008060,0x180000000,0x400002400000018,0x4241000200,0x100800000000,0x10201008400483,0xc008000208201000,0x800420000100,0x2010002000410,0x28041000000,0x4010080000024,0x400480010010080,0x200040028000008,0x100810084020,0x20c0401000080000,0x1000240000220000,0x4000020800,0x410000000480000,0x8004008000804201,0x806020000104000,0x2080002000211000,0x1001008001000,0x20000010024000,0x480200002040000,0x48200044008000,0x100000000010080,0x80090400042,0x41040200800200,0x4000020100110,0x2000400082200010,0x1008200000000040,0x2004800002,0x2002010000080,];let p=(x%4095)as usize;(SQTABLE_MOD4095[p>>6]>>(p&63))&1==1}pub fn$issq_newton(x:$x)->bool{let sqrt_f=$sqrt_newton(x);sqrt_f*sqrt_f==x}pub fn$issq(x:$x)->bool{$issq_mod32(x)&&$issq_mod4095(x)&&$issq_newton(x)}pub fn$sqrt_exact(x:$x)->Option<$x>{if$issq_mod32(x)&&$issq_mod4095(x){let sqrt_f=$sqrt_newton(x);if sqrt_f*sqrt_f==x{return Some(sqrt_f);}}None}};}fn_isqrt_n!(sqrt_floor,isqrt_64_exact,issq_u64_newton,issq_u64_mod32,issq_u64_mod48,issq_u64_mod4095,issq_u64,u64,32);fn_isqrt_n!(sqrt_floor,isqrt_32_exact,issq_u32_newton,issq_u32_mod32,issq_u32_mod48,issq_u32_mod4095,issq_u32,u32,16);}
pub mod jacobi {use crate::__cargo_equip::preludes::jacobi::*;use crate::__cargo_equip::crates::{invariant::*,primint::*};pub fn kronecker_i64(ai:i64,ni:i64)->i32{if ni==0{match ai{1|-1=>1,_=>0,}}else if ni<0{if ai<0{-kronecker_i64u64(ai,ni.wrapping_neg()as u64)}else{kronecker_i64u64(ai,ni.wrapping_neg()as u64)}}else{kronecker_i64u64(ai,ni as u64)}}pub fn kronecker_i64u64(ai:i64,n:u64)->i32{if n==0{match ai{1|-1=>1,_=>0,}}else if(n&1)==0{let trz=n.trailing_zeros();match ai&7{0|2|4|6=>0,1|7=>jacobi_i64(ai,n),3|5=>{if trz&1==0{jacobi_i64(ai,n>>trz)}else{-jacobi_i64(ai,n>>trz)}}_=>unreachable!(),}}else{jacobi_i64(ai,n)}}pub fn kronecker_u64(a:u64,n:u64)->i32{if n==0{match a{1=>1,_=>0,}}else if(n&1)==0{let trz=n.trailing_zeros();match a&7{0|2|4|6=>0,1|7=>jacobi_inner(a,n>>trz,1),3|5=>jacobi_inner(a,n>>trz,if trz&1==0{1}else{-1}),_=>unreachable!(),}}else{jacobi_inner(a,n,1)}}pub fn jacobi_i64(ai:i64,n:u64)->i32{debug_assert_eq!(n&1,1);if ai<0{jacobi_inner(ai.wrapping_neg()as u64,n,if(n&3)==3{-1}else{1},)}else{jacobi_inner(ai as u64,n,1)}}pub fn jacobi_i32(ai:i32,n:u32)->i32{debug_assert_eq!(n&1,1);if ai<0{jacobi_inner(ai.wrapping_neg()as u32,n,if(n&3)==3{-1}else{1},)}else{jacobi_inner(ai as u32,n,1)}}pub fn jacobi<U:UPrimInt>(a:U,n:U)->i32{debug_assert_eq!(n.as_u32()%2,1);jacobi_inner(a,n,1)}fn jacobi_inner<U:UPrimInt>(mut a:U,mut n:U,mut j:i32)->i32{while!a.is_zero()&&n>U::from(255){let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;if(a&n&U::from(3))==U::from(3){j=-j;}invariant!(!a.is_zero());let t=n%a;n=a;a=t;if a>(n>>1){a=n-a;if(n&U::from(3))==U::from(3){j=-j;}}}while!a.is_zero(){let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;if a<n{if a>(n>>1){a=n-a;if(n&U::from(3))==U::from(3){j=-j;}let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;}if(a&n&U::from(3))==U::from(3){j=-j;}let t=n-a;n=a;a=t;}else{a-=n;}}if n==U::from(1){j}else{0}}}
pub mod modint32dynamic {use crate::__cargo_equip::preludes::modint32dynamic::*;pub enum ModIntDynType{Zero,Odd,P0998244353,P1000000007,Power2,Even,}pub struct ModIntDyn{ty:ModIntDynType,m:u32,tz:u32,mx:u32,mimx:u32,mym:u32,dim:u64,dimx:u64,ib:[u32;64],}pub struct ModIntDynLight{ty:ModIntDynType,m:u32,dim:u64,mym:u32,}impl ModIntDyn{pub fn new_modulus(m:u32)->Self{if m==0{return Self{m,ty:ModIntDynType::Zero,tz:32,mx:1,mimx:0,mym:!0u32,dim:1,dimx:0,ib:[1u32;64],};}let tz=m.trailing_zeros();let mx=m>>tz;let mimx={let mut t=mx.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(mx));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t};let mym=u32::from(tz!=0).wrapping_neg()>>((32-tz)&31);let dim=((!0u64)/u64::from(m)).wrapping_add(1);let dimx=((!0u64)/u64::from(mx)).wrapping_add(1);let mut ib=[0u32;64];let mut t=1;for e in ib.iter_mut(){*e=t;t=t/2+((t%2).wrapping_neg()&(mx/2+1));}Self{m,ty:{if m==998_244_353{ModIntDynType::P0998244353}else if m==1_000_000_007{ModIntDynType::P1000000007}else if tz==0{ModIntDynType::Odd}else if mx==1{ModIntDynType::Power2}else{ModIntDynType::Even}},tz,mx,mimx,mym,dim,dimx,ib,}}}impl ModIntDynLight{pub fn new_modulus(m:u32)->Self{match m{0=>Self{ty:ModIntDynType::Zero,m,dim:1,mym:!0u32,},998_244_353=>Self{ty:ModIntDynType::P0998244353,m,dim:18479187003,mym:0,},1_000_000_007=>Self{ty:ModIntDynType::P1000000007,m,dim:18446743945,mym:0,},m if(m&m.wrapping_sub(1))==0=>Self{ty:ModIntDynType::Power2,m,dim:((!0u64)/u64::from(m)).wrapping_add(1),mym:m.wrapping_sub(1),},m if m%2==0=>Self{ty:ModIntDynType::Even,m,dim:((!0u64)/u64::from(m)).wrapping_add(1),mym:(m&m.wrapping_neg()).wrapping_sub(1),},_=>Self{ty:ModIntDynType::Odd,m,dim:((!0u64)/u64::from(m)).wrapping_add(1),mym:0,},}}}macro_rules!impl_modintdyn{($t:ty)=>{impl$t{pub fn modulus(&self)->u32{self.m}#[inline]pub fn norm(&self,a:u32)->u32{match self.ty{ModIntDynType::Zero=>a,ModIntDynType::Power2=>a&self.mym,_=>{if a>=self.m{a%self.m}else{a}}}}#[inline]pub fn add(&self,a:u32,b:u32)->u32{debug_assert!(a<self.m);debug_assert!(b<self.m);let v=u64::from(a)+u64::from(b);match self.ty{ModIntDynType::Zero=>v as u32,_=>match v.overflowing_sub(u64::from(self.m)){(_,true)=>v as u32,(w,false)=>w as u32,},}}#[inline]pub fn sub(&self,a:u32,b:u32)->u32{debug_assert!(a<self.m);debug_assert!(b<self.m);let(v,f)=a.overflowing_sub(b);match self.ty{ModIntDynType::Zero=>v,_=>v.wrapping_add(u32::from(f).wrapping_neg()&self.m),}}#[inline]pub fn neg(&self,a:u32)->u32{debug_assert!(a<self.m);self.sub(0,a)}#[inline]pub fn mul(&self,a:u32,b:u32)->u32{debug_assert!(a<self.m);debug_assert!(b<self.m);let z=u64::from(a)*u64::from(b);match self.ty{ModIntDynType::Power2=>(z as u32)&self.mym,ModIntDynType::P0998244353=>{(z-(((u128::from(z)*0x89AE_4087_5DE0_CC3F)>>93)as u64)*998_244_353)as u32}ModIntDynType::P1000000007=>{(z-(((u128::from(z)*0x8970_5F31_12A2_8FE5)>>93)as u64)*1_000_000_007)as u32}ModIntDynType::Zero=>z as u32,ModIntDynType::Odd|ModIntDynType::Even=>{let x=((u128::from(z)*u128::from(self.dim))>>64)as u64;let(v,f)=z.overflowing_sub(x.wrapping_mul(u64::from(self.m)));(v as u32).wrapping_add(u32::from(f).wrapping_neg()&self.m)}}}#[inline]pub fn pow(&self,a:u32,mut b:u32)->u32{debug_assert!(a<self.m);if b==0{return(self.m>1)as u32;}let mut t=a;while b%2==0{t=self.mul(t,t);b/=2;}let mut r=t;b/=2;while b!=0{t=self.mul(t,t);if b%2!=0{r=self.mul(r,t);}b/=2;}r}#[inline]pub fn div2(&self,a:u32)->u32{debug_assert_eq!(self.m%2,1);if a%2==0{a/2}else{(a/2)+(self.m/2)+1}}}};}impl_modintdyn!(ModIntDyn);impl_modintdyn!(ModIntDynLight);impl ModIntDyn{#[inline]fn mulmx(&self,a:u32,b:u32)->u32{debug_assert!(a<self.mx);debug_assert!(b<self.mx);let z=u64::from(a)*u64::from(b);match self.ty{ModIntDynType::P0998244353=>{(z-(((u128::from(z)*0x89AE_4087_5DE0_CC3F)>>93)as u64)*998_244_353)as u32}ModIntDynType::P1000000007=>{(z-(((u128::from(z)*0x8970_5F31_12A2_8FE5)>>93)as u64)*1_000_000_007)as u32}ModIntDynType::Power2|ModIntDynType::Zero=>0,ModIntDynType::Odd|ModIntDynType::Even=>{let x=((u128::from(z)*u128::from(self.dimx))>>64)as u64;let(v,f)=z.overflowing_sub(x.wrapping_mul(u64::from(self.mx)));(v as u32).wrapping_add(u32::from(f).wrapping_neg()&self.mx)}}}#[inline]pub fn div(&self,a:u32,b:u32)->Option<u32>{debug_assert!(a<self.m);debug_assert!(b<self.m);self.inv(b).map(|ib|self.mul(a,ib))}#[inline]pub fn inv_plain(&self,n:u32)->Option<u32>{let m=self.m;let(mut a,mut b,mut x,mut y)=(1,0,n,m);if m==1{return Some(0);}loop{match x{0=>return None,1=>return Some(a),_=>{}}b+=a*(y/x);y%=x;match y{0=>return None,1=>return Some(m-b),_=>{}}a+=b*(x/y);x%=y;}}#[inline]fn inv_mx(&self,n:u32)->Option<u32>{debug_assert_ne!(self.mx%2,0);if self.mx%2==0{unsafe{core::hint::unreachable_unchecked()}}if self.mx==1{return Some(0);}let(mut a,mut b,mut x,mut y)=(1,0,n,self.mx);if x==0{return None;}let mut s=x.trailing_zeros();x>>=s;loop{if x==1{return Some(self.mulmx(a,self.ib[s as usize]));}if x==y{return None;}if x<=(y>>3){if x==0{unsafe{core::hint::unreachable_unchecked()}}b+=a*(y/x);y%=x;if y==0{return None;}let t=y.trailing_zeros();y>>=t;a<<=t;s+=t;}else{while x<y{b+=a;y-=x;let t=y.trailing_zeros();y>>=t;a<<=t;s+=t;}}if y==1{return Some(self.mulmx(self.mx-b,self.ib[s as usize]));}if(x>>3)>=y{if y==0{unsafe{core::hint::unreachable_unchecked()}}a+=b*(x/y);x%=y;if x==0{return None;}let t=x.trailing_zeros();x>>=t;b<<=t;s+=t;}else{while x>y{a+=b;x-=y;let t=x.trailing_zeros();x>>=t;b<<=t;s+=t;}}}}#[inline]fn inv_my(&self,n:u32)->Option<u32>{if self.mym==0{return Some(0);}if n%2==0{return None;}Some(match self.tz{21..=0xffff_ffff=>{let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t}11..=20=>{let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t}6..=10=>{let t=n.wrapping_mul(3)^2;t.wrapping_mul(2u32.wrapping_sub(n.wrapping_mul(t)))}4..=5=>n.wrapping_mul(3)^2,0..=3=>n,}&self.mym,)}#[inline]pub fn inv(&self,n:u32)->Option<u32>{match self.ty{ModIntDynType::Power2=>self.inv_my(n),ModIntDynType::P0998244353|ModIntDynType::P1000000007|ModIntDynType::Odd=>{self.inv_mx(n)}ModIntDynType::Even=>{if let Some(y)=self.inv_my(n){if let Some(x)=self.inv_mx(n){let(t,f)=x.overflowing_sub(self.mx*(self.mimx.wrapping_mul(x.wrapping_sub(y))&self.mym),);return Some(t.wrapping_add(u32::from(f).wrapping_neg()&self.m));}}None}ModIntDynType::Zero=>{if n%2==0{return None;}let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));Some(t)}}}}}
pub mod montodd {use crate::__cargo_equip::preludes::montodd::*;use crate::__cargo_equip::crates::invariant::*;pub trait MontVal<T,BitCountType=u32>{fn m(&self)->T;fn mi(&self)->T;fn mh(&self)->T;fn r(&self)->T;fn rn(&self)->T;fn r2(&self)->T;fn d(&self)->T;fn k(&self)->BitCountType;}pub trait MontOps<T,BitCountType=u32>{fn add(&self,a:T,b:T)->T;fn sub(&self,a:T,b:T)->T;fn div2(&self,ar:T)->T;fn mrmul(&self,ar:T,br:T)->T;fn mr(&self,ar:T)->T;fn ar(&self,a:T)->T;fn pow(&self,ar:T,b:T)->T;}pub trait MontModN<T,BitCountType=u32>{fn modn(&self,x:T)->T;}pub trait MontNew<T,U=T,BitCountType=u32>{fn new_modulus(n:T)->Self;}pub struct Mont<T,BitCountType=u32>{m:T,mi:T,mh:T,r:T,rn:T,r2:T,d:T,k:BitCountType,}macro_rules!impl_mont_val_pr{($x:ty)=>{impl MontVal<$x>for Mont<$x>{fn m(&self)->$x{self.m}fn mi(&self)->$x{self.mi}fn mh(&self)->$x{self.mh}fn r(&self)->$x{self.r}fn rn(&self)->$x{self.rn}fn r2(&self)->$x{self.r2}fn d(&self)->$x{self.d}fn k(&self)->u32{self.k}}};}impl_mont_val_pr!(u64);impl_mont_val_pr!(u32);fn mont_r2_u64(m:u64)->(u64,u64){(((1u64.wrapping_neg()%m).wrapping_add(1)),(((1u128.wrapping_neg()%(m as u128))as u64).wrapping_add(1)),)}fn mont_r2_u32(m:u32)->(u32,u32){(((1u32.wrapping_neg()%m).wrapping_add(1)),(((1u64.wrapping_neg()%(m as u64))as u32).wrapping_add(1)),)}fn mont_sub_u64(a:u64,b:u64,m:u64)->u64{let(t,f)=a.overflowing_sub(b);t.wrapping_add((f as u64).wrapping_neg()&m)}fn mont_sub_u32(a:u32,b:u32,m:u32)->u32{let(t,f)=a.overflowing_sub(b);t.wrapping_add((f as u32).wrapping_neg()&m)}macro_rules!impl_mont_ops{($x:ty,$y:ty,$y2:ty,$w:literal,$msub:ident)=>{impl MontOps<$y>for$x{fn add(&self,a:$y,b:$y)->$y{debug_assert!(a<self.m());debug_assert!(b<self.m());$msub(a,self.m()-b,self.m())}fn sub(&self,a:$y,b:$y)->$y{debug_assert!(a<self.m());debug_assert!(b<self.m());$msub(a,b,self.m())}fn div2(&self,ar:$y)->$y{debug_assert!(ar<self.m());let t=ar>>1;t.wrapping_add((((ar&1)!=0)as$y).wrapping_neg()&self.mh())}fn mrmul(&self,ar:$y,br:$y)->$y{debug_assert!(ar<self.m());debug_assert!(br<self.m());let(m,mi)=(self.m(),self.mi());let t:$y2=(ar as$y2)*(br as$y2);$msub((t>>$w)as$y,(((((t as$y).wrapping_mul(mi))as$y2)*(m as$y2))>>$w)as$y,m,)}fn mr(&self,ar:$y)->$y{debug_assert!(ar<self.m());let(m,mi)=(self.m(),self.mi());$msub(0,((((ar.wrapping_mul(mi))as$y2)*(m as$y2))>>$w)as$y,m,)}fn ar(&self,a:$y)->$y{debug_assert!(a<self.m());self.mrmul(a,self.r2())}fn pow(&self,mut ar:$y,mut b:$y)->$y{debug_assert!(ar<self.m());if b==0{return self.r();}while b&1==0{ar=self.mrmul(ar,ar);b>>=1;}let mut t=ar;b>>=1;while b!=0{ar=self.mrmul(ar,ar);if(b&1)!=0{t=self.mrmul(t,ar);}b>>=1;}t}}};}impl_mont_ops!(Mont<u64>,u64,u128,64,mont_sub_u64);impl_mont_ops!(Mont<u32>,u32,u64,32,mont_sub_u32);macro_rules!impl_mont_modn{($x:ty)=>{impl MontModN<$x>for Mont<$x>{fn modn(&self,x:$x)->$x{if x<self.m(){x}else{x%self.m()}}}};}impl_mont_modn!(u64);impl_mont_modn!(u32);macro_rules!impl_mont_new{($x:ty,$x2:ty,$mont_r2:ident)=>{impl MontNew<$x>for Mont<$x>{fn new_modulus(m:$x)->Self{debug_assert!(m>1&&(m&1)==1);let mi={let bits=(!(0 as$x)).count_ones();let mut x=m.wrapping_mul(3)^2;let mut y=(1 as$x).wrapping_sub(m.wrapping_mul(x));let mut w=5;while w<bits{x=x.wrapping_mul(y.wrapping_add(1));y=y.wrapping_mul(y);w*=2;}x};debug_assert_eq!(m.wrapping_mul(mi),1);let mh=(m>>1)+1;invariant!(m!=0);let(r,r2)=$mont_r2(m);let rn=m-r;let mut d=m-1;let k=d.trailing_zeros();d>>=k;debug_assert_eq!(Self{m,mi,mh,r,rn,r2,d,k}.mr(r),1);debug_assert_eq!(Self{m,mi,mh,r,rn,r2,d,k}.mrmul(1,r2),r);Self{m,mi,mh,r,rn,r2,d,k,}}}};}impl_mont_new!(u64,u128,mont_r2_u64);impl_mont_new!(u32,u64,mont_r2_u32);}
pub mod sqrt {use crate::__cargo_equip::preludes::sqrt::*;use crate::__cargo_equip::crates::{invariant::*,primint::*};pub fn sqrt_floor<U:UPrimInt>(x:U)->U{if x<=U::one(){return x;}if U::BITS>32&&x<=U::from_u32(!0u32){U::from_u32(sqrt_floor(x.as_u32()))}else if U::BITS<=32||x>U::from_u64(!0u64){let y=(x-U::one()).leading_zeros();let log2=U::BITS-1-y;let k=(U::BITS>>1)-(y>>1);let mut s=U::one()<<k;let mut t=(s+(x>>k))>>1;for _ in 0..match log2{0..=3=>0,4..=9=>1,10..=22=>2,23..=47=>3,48..=98=>4,99..=199=>5,_=>32,}{if t>=s{return s;}s=t;invariant!(!s.is_zero());t=(s+x/s)>>1;}match t.checked_mul(t){Some(u)if u<=x=>t,_=>t-U::one(),}}else{use std::cmp::Ordering::*;let x=x.as_u64();match x{0..=0xfffffffc00000003=>{let mut s=(x as f64).sqrt()as u64;U::from_u64(match((s+1)*(s+1)).cmp(&x){Less=>loop{s+=1;match((s+1)*(s+1)).cmp(&x){Less=>{}Equal=>break s+1,Greater=>break s,}},Equal=>s+1,Greater=>{while s*s>x{s-=1;}s}})}0xfffffffc00000004..=0xfffffffe00000000=>U::from_u32((!0u32)-1),0xfffffffe00000001..=0xffffffffffffffff=>U::from_u32(!0u32),}}}pub fn sqrt_ceil<U:UPrimInt>(x:U)->U{let s=sqrt_floor(x);if x>s*s{s+U::one()}else{s}}}
pub mod xorshift {#[derive(Copy,Clone,Debug)]pub struct Xorshift64{x:u64,}impl Xorshift64{pub fn new()->Self{Self{x:88_172_645_463_325_252,}}pub fn systime()->Self{Self{x:std::time::SystemTime::now().duration_since(std::time::SystemTime::UNIX_EPOCH).map(|d|d.as_nanos()as u64).unwrap_or(88_172_645_463_325_252),}}pub fn raw(x:u64)->Self{Self{x}}pub fn next_u64(&mut self)->u64{self.x^=self.x<<13;self.x^=self.x>>7;self.x^=self.x<<17;self.x}}impl Default for Xorshift64{fn default()->Self{Self::new()}}impl Iterator for Xorshift64{type Item=u64;fn next(&mut self)->Option<u64>{Some(self.next_u64())}}}
pub mod invariant {pub use crate::__cargo_equip::macros::invariant::*;#[macro_export]macro_rules!__cargo_equip_macro_def_invariant_invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}macro_rules!invariant{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_invariant_invariant!{$($tt)*})}}
pub mod primint {use std::ops;pub trait UPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+ops::AddAssign+ops::SubAssign+ops::MulAssign+ops::DivAssign+ops::RemAssign+ops::Shl<u32,Output=Self>+ops::Shr<u32,Output=Self>+ops::ShlAssign<u32>+ops::ShrAssign<u32>+ops::BitAnd<Output=Self>+ops::BitOr<Output=Self>+ops::BitXor<Output=Self>+ops::BitAndAssign+ops::BitOrAssign+ops::BitXorAssign+std::convert::From<u8>{const BITS:u32;fn count_zeros(self)->u32;fn trailing_zeros(self)->u32;fn leading_zeros(self)->u32;fn checked_add(self,rhs:Self)->Option<Self>;fn checked_sub(self,rhs:Self)->Option<Self>;fn checked_mul(self,rhs:Self)->Option<Self>;fn checked_pow(self,exp:u32)->Option<Self>;fn wrapping_add(self,rhs:Self)->Self;fn wrapping_sub(self,rhs:Self)->Self;fn wrapping_neg(self)->Self;fn wrapping_mul(self,rhs:Self)->Self;fn overflowing_add(self,rhs:Self)->(Self,bool);fn overflowing_sub(self,rhs:Self)->(Self,bool);fn overflowing_neg(self)->(Self,bool);fn overflowing_mul(self,rhs:Self)->(Self,bool);fn pow(self,exp:u32)->Self;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;fn as_u8(self)->u8;fn as_u16(self)->u16;fn as_u32(self)->u32;fn as_u64(self)->u64;fn as_u128(self)->u128;fn as_usize(self)->usize;fn from_u32(x:u32)->Self;fn from_u64(x:u64)->Self;fn from_u128(x:u128)->Self;fn from_usize(x:usize)->Self;}macro_rules!impl_uprimint{($t:ty)=>{impl UPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn count_zeros(self)->u32{self.count_zeros()}fn trailing_zeros(self)->u32{self.trailing_zeros()}fn leading_zeros(self)->u32{self.leading_zeros()}fn checked_add(self,rhs:$t)->Option<$t>{self.checked_add(rhs)}fn checked_sub(self,rhs:$t)->Option<$t>{self.checked_sub(rhs)}fn checked_mul(self,rhs:$t)->Option<$t>{self.checked_mul(rhs)}fn checked_pow(self,exp:u32)->Option<$t>{self.checked_pow(exp)}fn wrapping_add(self,rhs:$t)->$t{self.wrapping_add(rhs)}fn wrapping_sub(self,rhs:$t)->$t{self.wrapping_sub(rhs)}fn wrapping_neg(self)->$t{self.wrapping_neg()}fn wrapping_mul(self,rhs:$t)->$t{self.wrapping_mul(rhs)}fn overflowing_add(self,rhs:$t)->($t,bool){self.overflowing_add(rhs)}fn overflowing_sub(self,rhs:$t)->($t,bool){self.overflowing_sub(rhs)}fn overflowing_neg(self)->($t,bool){self.overflowing_neg()}fn overflowing_mul(self,rhs:$t)->($t,bool){self.overflowing_mul(rhs)}fn pow(self,exp:u32)->Self{self.pow(exp)}fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}fn as_u8(self)->u8{self as u8}fn as_u16(self)->u16{self as u16}fn as_u32(self)->u32{self as u32}fn as_u64(self)->u64{self as u64}fn as_u128(self)->u128{self as u128}fn as_usize(self)->usize{self as usize}fn from_u32(x:u32)->Self{x as Self}fn from_u64(x:u64)->Self{x as Self}fn from_u128(x:u128)->Self{x as Self}fn from_usize(x:usize)->Self{x as Self}}};}impl_uprimint!(u8);impl_uprimint!(u16);impl_uprimint!(u32);impl_uprimint!(u64);impl_uprimint!(u128);impl_uprimint!(usize);pub trait IPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Neg<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+std::convert::From<i8>{const BITS:u32;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;}macro_rules!impl_iprimint{($t:ty)=>{impl IPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}}};}impl_iprimint!(i8);impl_iprimint!(i16);impl_iprimint!(i32);impl_iprimint!(i64);impl_iprimint!(i128);impl_iprimint!(isize);}
pub mod bpsw {use crate::__cargo_equip::preludes::bpsw::*;use crate::__cargo_equip::crates::{issq::*,jacobi::*};pub use crate::__cargo_equip::crates::{montodd::*,primint::*};pub trait PrimeTest<U>{fn primetest_base2(&self)->bool;fn primetest_miller(&self,base:U)->bool;fn primetest_lucas(&self)->bool;fn primetest_bpsw(&self)->bool;}pub fn lucas_dprobe<U:UPrimInt>(n:U)->Option<i32>{for d in(5u32..).step_by(2){match if(n&U::from(3))==U::from(3)&&(d&3)==3{-jacobi(U::from_u32(d),n)}else{jacobi(U::from_u32(d),n)}{-1=>{return Some(if(d&2)==0{d as i32}else{-(d as i32)});}0=>{if U::from_u32(d)<n{return None;}}_=>{}}if d==61&&issq_u64(n.as_u64()){return None;}}None}macro_rules!trait_primetest{($jacobi:ident,$issq:ident,$u:ty,$i:ty,$w:literal)=>{impl PrimeTest<$u>for Mont<$u>{fn primetest_base2(&self)->bool{let(r,rn,d,k)=(self.r(),self.rn(),self.d(),self.k());let mut br=self.pow(self.add(r,r),d);if br==r||br==rn{return true;}for _ in 1..k{br=self.mrmul(br,br);if br==rn{return true;}}false}fn primetest_miller(&self,mut base:$u)->bool{let(m,r,rn,d,k)=(self.m(),self.r(),self.rn(),self.d(),self.k());if base>=m{base=self.modn(base);if base==0{return true;}}let mut tr=self.pow(self.ar(base),d);if tr==r||tr==rn{return true;}for _ in 1..k{tr=self.mrmul(tr,tr);if tr==rn{return true;}}false}fn primetest_lucas(&self)->bool{let n=self.m();let d=match lucas_dprobe(n){Some(d)=>d,None=>return false,};let qm=self.ar(self.modn(if d<0{((1-d)as$u)/4}else{n-((d-1)as$u)/4}));let mut k=(n+1)<<(n+1).leading_zeros();let mut um=self.r();let mut vm=self.r();let mut qn=qm;let dm=self.ar(if d<0{n-self.modn((-d)as$u)}else{self.modn(d as$u)});k<<=1;while k!=0{um=self.mrmul(um,vm);vm=self.sub(self.mrmul(vm,vm),self.add(qn,qn));qn=self.mrmul(qn,qn);if(k>>($w-1))!=0{let uu=self.div2(self.add(um,vm));vm=self.div2(self.add(self.mrmul(dm,um),vm));um=uu;qn=self.mrmul(qn,qm);}k<<=1;}if um==0||vm==0{return true;}let mut x=(n+1)&(!n);x>>=1;while x!=0{um=self.mrmul(um,vm);vm=self.sub(self.mrmul(vm,vm),self.add(qn,qn));if vm==0{return true;}qn=self.mrmul(qn,qn);x>>=1;}false}fn primetest_bpsw(&self)->bool{self.primetest_base2()&&self.primetest_lucas()}}};}trait_primetest!(jacobi_i64,issq_u64,u64,i64,64);trait_primetest!(jacobi_i32,issq_u32,u32,i32,32);pub fn primetest_u64_bpsw(n:u64)->bool{if n==2{return true;}if n==1||(n&1)==0{return false;}let mont=Mont::<u64>::new_modulus(n);mont.primetest_bpsw()}}
pub mod miller_rabin_fj32_256 {use crate::__cargo_equip::preludes::miller_rabin_fj32_256::*;pub use crate::__cargo_equip::crates::modint32dynamic::*;const FJ32_256_BASES:[u16;256]=[15591,2018,166,7429,8064,16045,10503,4399,1949,1295,2776,3620,560,3128,5212,2657,2300,2021,4652,1471,9336,4018,2398,20462,10277,8028,2213,6219,620,3763,4852,5012,3185,1333,6227,5298,1074,2391,5113,7061,803,1269,3875,422,751,580,4729,10239,746,2951,556,2206,3778,481,1522,3476,481,2487,3266,5633,488,3373,6441,3344,17,15105,1490,4154,2036,1882,1813,467,3307,14042,6371,658,1005,903,737,1887,7447,1888,2848,1784,7559,3400,951,13969,4304,177,41,19875,3110,13221,8726,571,7043,6943,1199,352,6435,165,1169,3315,978,233,3003,2562,2994,10587,10030,2377,1902,5354,4447,1555,263,27027,2283,305,669,1912,601,6186,429,1930,14873,1784,1661,524,3577,236,2360,6146,2850,55637,1753,4178,8466,222,2579,2743,2031,2226,2276,374,2132,813,23788,1610,4422,5159,1725,3597,3366,14336,579,165,1375,10018,12616,9816,1371,536,1867,10864,857,2206,5788,434,8085,17618,727,3639,1595,4944,2129,2029,8195,8344,6232,9183,8126,1870,3296,7455,8947,25017,541,19115,368,566,5674,411,522,1027,8215,2050,6544,10049,614,774,2333,3007,35201,4706,1152,1785,1028,1540,3743,493,4474,2521,26845,8354,864,18915,5465,2447,42,4511,1660,166,1249,6259,2553,304,272,7286,73,6554,899,2816,5197,13330,7054,2818,3199,811,922,350,7514,4452,3449,2663,4708,418,1621,1171,3471,88,11345,412,1559,194,];pub trait MillerFJ32_256{fn primetest_miller_fj32_256(&self)->bool;}macro_rules!impl_miller{($t:ty)=>{impl MillerFJ32_256 for$t{fn primetest_miller_fj32_256(&self)->bool{let m=self.modulus();match m{2|3|5|7=>return true,x if x%2==0||x%3==0||x%5==0||x%7==0=>return false,x if x<121=>return x>1,_=>{}}let mut h=m as u64;h=((h>>16)^h).wrapping_mul(0x45d9f3b);h=((h>>16)^h).wrapping_mul(0x45d9f3b);h=((h>>16)^h)&255;let a=FJ32_256_BASES[h as usize]as u32;let m1=m-1;let s=m1.trailing_zeros();let mut cur=self.pow(if m>a{a}else{a%m},m1>>s);if cur==1||cur==m1{return true;}for _ in 1..s{cur=self.mul(cur,cur);if cur==m1{return true;}}false}}};}impl_miller!(ModIntDyn);impl_miller!(ModIntDynLight);pub fn primetest_miller_fj32_256(n:u32)->bool{if n<=2||(n&1)==0{return n==2;}let mint=ModIntDynLight::new_modulus(n);mint.primetest_miller_fj32_256()}}
pub mod rho {use crate::__cargo_equip::preludes::rho::*;use crate::__cargo_equip::crates::{bpsw::*,invariant::*,miller_rabin_fj32_256::*,xorshift::*};pub use crate::__cargo_equip::crates::{modint32dynamic::*,montodd::*};pub trait Factorize<T>{fn find_factor(&self)->T;}impl Factorize<u64>for Mont<u64>{fn find_factor(&self)->u64{let n=self.m();fn bingcd_yodd(mut x:u64,mut y:u64)->u64{invariant!(y%2==1);if x==0{return y;}x>>=x.trailing_zeros();while x!=y{let(s,t)=if x>y{(x-y,y)}else{(y-x,x)};x=s>>s.trailing_zeros();y=t;}y}let mut rng=Xorshift64::new();let m=1024u64;let mut c=n-1;let mut y0=0;loop{let mut x=0;let mut y=y0;let mut ys=0;let mut g=1;let mut q=1;let mut r=1;let mut k=0;while g==1&&r<=(1<<20){x=y;while k<r&&g==1{ys=y;for _ in 0..(m.min(r-k)){y=self.sub(self.mrmul(y,y),c);q=self.mrmul(q,self.sub(x,y));}g=bingcd_yodd(q,n);k+=m;}k=r;r*=2;}if g==n{g=1;y=ys;while g==1{y=self.sub(self.mrmul(y,y),c);g=bingcd_yodd(self.sub(x,y),n);}}if g!=1&&g!=n{return g;}y0=((((rng.next_u64()as u128)*((n-2)as u128))>>64)as u64)+2;c=((((rng.next_u64()as u128)*((n-1)as u128))>>64)as u64)+1;}}}impl Factorize<u32>for ModIntDynLight{fn find_factor(&self)->u32{let n=self.modulus();fn bingcd_yodd_32(mut x:u32,mut y:u32)->u32{invariant!(y%2==1);if x==0{return y;}x>>=x.trailing_zeros();while x!=y{let(s,t)=if x>y{(x-y,y)}else{(y-x,x)};x=s>>s.trailing_zeros();y=t;}y}let mut rng=Xorshift64::new();let m=1024u64;let mut c=n-1;let mut y0=0;loop{let mut x=0;let mut y=y0;let mut ys=0;let mut g=1;let mut q=1;let mut r=1;let mut k=0;while g==1&&r<=(1<<20){x=y;while k<r&&g==1{ys=y;for _ in 0..(m.min(r-k)){y=self.sub(self.mul(y,y),c);q=self.mul(q,self.sub(x,y));}g=bingcd_yodd_32(q,n);k+=m;}k=r;r*=2;}if g==n{g=1;y=ys;while g==1{y=self.sub(self.mul(y,y),c);g=bingcd_yodd_32(self.sub(x,y),n);}}if g!=1&&g!=n{return g;}y0=((((rng.next_u64()as u128)*((n-2)as u128))>>64)as u32)+2;c=((((rng.next_u64()as u128)*((n-1)as u128))>>64)as u32)+1;}}}pub const fn u64_abs_diff_shim(a:u64,b:u64)->u64{let(v,(w,f))=(b.wrapping_sub(a),a.overflowing_sub(b));((f as u64).wrapping_neg()&v)|(!(f as u64).wrapping_neg()&w)}pub fn factorize(mut n:u64)->Vec<u64>{let mut x=Vec::with_capacity(64);while(n&1)==0{n>>=1;invariant!(x.len()<x.capacity());x.push(2);}while(n%3)==0{n/=3;invariant!(x.len()<x.capacity());x.push(3);}if n>1{let mut i=x.len();invariant!(x.len()<x.capacity());x.push(n);while i<x.len(){match{if x[i]<=0xffff_ffff{let mint=ModIntDynLight::new_modulus(x[i]as u32);let isprime=mint.primetest_miller_fj32_256();if isprime{None}else{Some(mint.find_factor()as u64)}}else{let mont=Mont::new_modulus(x[i]);let isprime=mont.primetest_bpsw();if isprime{None}else{Some(mont.find_factor())}}}{None=>{i+=1;}Some(f)=>{x[i]/=f;invariant!(x.len()<x.capacity());x.push(f);}}}}x.sort_unstable();x}}
}
pub(crate) mod macros {
pub mod issq {}
pub mod jacobi {}
pub mod modint32dynamic {}
pub mod montodd {}
pub mod sqrt {}
pub mod xorshift {}
pub mod invariant {pub use crate::__cargo_equip_macro_def_invariant_invariant as invariant;}
pub mod primint {}
pub mod bpsw {}
pub mod miller_rabin_fj32_256 {}
pub mod rho {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod issq {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint,sqrt};}
pub mod jacobi {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
pub mod modint32dynamic {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::invariant;}
pub mod montodd {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::invariant;}
pub mod sqrt {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
pub mod xorshift {}
pub mod invariant {}
pub mod primint {}
pub mod bpsw {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,issq,jacobi,montodd,primint};}
pub mod miller_rabin_fj32_256 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::modint32dynamic;}
pub mod rho {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{bpsw,invariant,miller_rabin_fj32_256,modint32dynamic,montodd,sqrt,xorshift};}
}
}