結果

問題 No.2379 Burnside's Theorem
ユーザー sakikuroesakikuroe
提出日時 2023-07-14 21:27:23
言語 Rust
(1.77.0 + proconio)
結果
WA  
実行時間 -
コード長 6,648 bytes
コンパイル時間 13,277 ms
コンパイル使用メモリ 401,428 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-16 06:15:28
合計ジャッジ時間 12,898 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 WA -
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 WA -
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 1 ms
6,944 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 1 ms
6,940 KB
testcase_21 AC 1 ms
6,944 KB
testcase_22 WA -
testcase_23 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[macro_export]
macro_rules! read_line { ($($xs: tt)*) => { let mut buf = String::new(); std::io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); expand!(iter, $($xs)*); }; }
macro_rules! expand { ($iter: expr,) => {}; ($iter: expr, mut $var: ident : $type: tt, $($xs: tt)*) => { let mut $var = value!($iter, $type); expand!($iter, $($xs)*); }; ($iter: expr, $var: ident : $type: tt, $($xs: tt)*) => { let $var = value!($iter, $type); expand!($iter, $($xs)*); }; }
macro_rules! value { ($iter:expr, ($($type: tt),*)) => { ($(value!($iter, $type)),*) }; ($iter: expr, [$type: tt; $len: expr]) => { (0..$len).map(|_| value!($iter, $type)).collect::<Vec<_>>() }; ($iter: expr, Chars) => { value!($iter, String).unwrap().chars().collect::<Vec<_>>() }; ($iter: expr, $type: ty) => { if let Some(v) = $iter.next() { v.parse::<$type>().ok() } else { None } }; }

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.into_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 main() {
    read_line!(n: usize,);
    let n = n.unwrap();

    let mut qe = factorize(n);
    qe.sort();
    qe.dedup();

    println!("{}", if qe.len() == 2 { "Yes" } else { "No" });
}
0