結果

問題 No.732 3PrimeCounting
ユーザー Kohei Asano
提出日時 2020-01-15 09:56:25
言語 Rust
(1.40.0)
結果
AC  
実行時間 1,184 ms
コード長 11,049 Byte
コンパイル時間 1,592 ms
使用メモリ 24,024 KB
最終ジャッジ日時 2020-01-15 09:56:46

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
case1.txt AC 0 ms
1,924 KB
case2.txt AC 0 ms
1,860 KB
case3.txt AC 0 ms
1,908 KB
case4.txt AC 0 ms
1,948 KB
case5.txt AC 0 ms
1,960 KB
case6.txt AC 0 ms
2,016 KB
case7.txt AC 0 ms
1,940 KB
case8.txt AC 0 ms
1,888 KB
case9.txt AC 0 ms
2,016 KB
case10.txt AC 0 ms
2,056 KB
case11.txt AC 0 ms
1,876 KB
case12.txt AC 4 ms
2,076 KB
case13.txt AC 4 ms
2,072 KB
case14.txt AC 4 ms
1,876 KB
case15.txt AC 4 ms
1,936 KB
case16.txt AC 4 ms
2,004 KB
case17.txt AC 4 ms
2,028 KB
case18.txt AC 4 ms
1,944 KB
case19.txt AC 4 ms
2,028 KB
case20.txt AC 4 ms
2,108 KB
case21.txt AC 4 ms
2,052 KB
case22.txt AC 16 ms
2,356 KB
case23.txt AC 16 ms
2,416 KB
case24.txt AC 0 ms
2,008 KB
case25.txt AC 4 ms
1,900 KB
case26.txt AC 28 ms
2,732 KB
case27.txt AC 28 ms
2,604 KB
case28.txt AC 8 ms
2,264 KB
case29.txt AC 4 ms
2,152 KB
case30.txt AC 12 ms
2,104 KB
case31.txt AC 16 ms
2,204 KB
case32.txt AC 16 ms
2,504 KB
case33.txt AC 24 ms
2,668 KB
case34.txt AC 24 ms
2,876 KB
case35.txt AC 24 ms
2,760 KB
case36.txt AC 28 ms
2,552 KB
case37.txt AC 24 ms
2,624 KB
case38.txt AC 4 ms
2,000 KB
case39.txt AC 4 ms
2,060 KB
case40.txt AC 24 ms
2,660 KB
case41.txt AC 12 ms
2,412 KB
case42.txt AC 16 ms
2,496 KB
case43.txt AC 16 ms
2,420 KB
case44.txt AC 12 ms
2,316 KB
case45.txt AC 16 ms
2,432 KB
case46.txt AC 8 ms
2,172 KB
case47.txt AC 4 ms
2,072 KB
case48.txt AC 12 ms
2,336 KB
case49.txt AC 32 ms
2,676 KB
case50.txt AC 32 ms
2,792 KB
case51.txt AC 12 ms
2,400 KB
case52.txt AC 16 ms
2,396 KB
case53.txt AC 4 ms
2,228 KB
case54.txt AC 64 ms
3,468 KB
case55.txt AC 556 ms
13,232 KB
case56.txt AC 552 ms
13,244 KB
case57.txt AC 548 ms
13,316 KB
case58.txt AC 140 ms
5,064 KB
case59.txt AC 140 ms
5,020 KB
case60.txt AC 68 ms
4,064 KB
case61.txt AC 252 ms
7,584 KB
case62.txt AC 252 ms
7,540 KB
case63.txt AC 556 ms
14,676 KB
case64.txt AC 308 ms
8,396 KB
case65.txt AC 252 ms
7,848 KB
case66.txt AC 252 ms
7,916 KB
case67.txt AC 0 ms
1,976 KB
case68.txt AC 4 ms
1,976 KB
case69.txt AC 548 ms
13,572 KB
case70.txt AC 552 ms
13,668 KB
case71.txt AC 552 ms
13,192 KB
case72.txt AC 552 ms
13,344 KB
case73.txt AC 304 ms
8,328 KB
case74.txt AC 688 ms
18,604 KB
case75.txt AC 688 ms
18,548 KB
case76.txt AC 28 ms
2,720 KB
case77.txt AC 548 ms
13,632 KB
case78.txt AC 144 ms
6,108 KB
case79.txt AC 672 ms
14,724 KB
case80.txt AC 552 ms
13,632 KB
case81.txt AC 672 ms
14,612 KB
case82.txt AC 548 ms
13,300 KB
case83.txt AC 4 ms
2,108 KB
case84.txt AC 144 ms
5,188 KB
case85.txt AC 248 ms
7,328 KB
case86.txt AC 548 ms
13,060 KB
case87.txt AC 672 ms
14,496 KB
case88.txt AC 1,180 ms
23,980 KB
case89.txt AC 1,184 ms
24,024 KB
テストケース一括ダウンロード
コンパイルメッセージ
warning: unused macro definition
  --> Main.rs:1:1
   |
1  | / macro_rules! input {
2  | |     (source = $s:expr, $($r:tt)*) => {
3  | |         let mut iter = $s.split_whitespace();
4  | |         input_inner!{iter, $($r)*}
...  |
15 | |     };
16 | | }
   | |_^
   |
   = note: `#[warn(unused_macros)]` on by default

warning: unused macro definition
  --> Main.rs:17:1
   |
17 | / macro_rules! input_inner {
18 | |     ($iter:expr) => {};
19 | |     ($iter:expr, ) => {};
20 | |     // var... 変数の識別子, $t...型を一つよむ
...  |
25 | |     };
26 | | }
   | |_^

warning: unused macro definition
  --> Main.rs:27:1
   |
27 | / macro_rules! read_value {
28 | |     ($iter:expr, ( $($t:tt),* )) => {
29 | |         ( $(read_value!($iter, $t)),* )
30 | |     };
...  |
44 | |     };
45 | | }
   | |_^

warning: function is never used: `mod_pow`
   --> Main.rs:316:1
    |
316 | fn mod_pow(mut a: u64, mut n: u64, m: u64) -> u64 {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: function is never used: `mod_inv`
   --> Main.rs:330:1
    |
330 | fn mod_inv(a: u64, m: u64) -> u64 {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: function is never used: `garner`
   --> Main.rs:333:1
    |
333 | fn garner(mr: &mut Vec<(u64, u64)>, m: u64) -> u64 {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff #
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    // var... 変数の識別子, $t...型を一つよむ
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        //ここで繰り返し
        input_inner!{$iter $($r)*}
    };
}
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    //
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    // 配列の最後のNestではここで型が指定されてparseされる
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    // var... 変数の識別子, $t...型を一つよむ
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        //ここで繰り返し
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    //
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    // 配列の最後のNestではここで型が指定されてparseされる
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// =========
pub trait ModI:
    Sized
    + PartialEq
    + Copy
    + std::ops::Add<Output = Self>
    + std::ops::Sub<Output = Self>
    + std::ops::Mul<Output = Self>
    + std::ops::Div<Output = Self>
    + std::ops::AddAssign
    + std::ops::SubAssign
    + std::ops::MulAssign
    + std::ops::DivAssign
    + std::default::Default
    + std::fmt::Display
    + std::fmt::Debug
{
    fn m() -> u64;
    fn new(x: u64) -> Self;
    fn pow(self, n: u64) -> Self;
    fn inv(&self) -> Self;
}
macro_rules! define_modint {
    ($n:ident,$m:expr) => {
        #[derive(Clone, Copy, Eq, PartialEq, PartialOrd, Ord)]
        struct $n(u64);

        #[allow(dead_code)]
        impl ModI for $n {
            fn m() -> u64 {
                $m
            }
            fn new(x: u64) -> $n {
                $n(x % $m)
            }

            fn pow(self, mut n: u64) -> $n {
                let mut ret = $n::new(1);
                let mut base = self;
                while n > 0 {
                    if n & 1 == 1 {
                        ret *= base;
                    }
                    base *= base;
                    n >>= 1;
                }
                ret
            }

            fn inv(&self) -> $n {
                self.pow($m - 2)
            }
        }

        impl std::default::Default for $n {
            fn default() -> $n {
                $n::new(0u64)
            }
        }

        impl std::convert::From<u64> for $n {
            fn from(x: u64) -> $n {
                $n::new(x)
            }
        }

        // Binary operator
        impl std::ops::Add for $n {
            type Output = $n;
            fn add(self, rhs: $n) -> Self::Output {
                $n::new(self.0 + rhs.0)
            }
        }

        impl std::ops::Sub for $n {
            type Output = $n;
            fn sub(self, rhs: $n) -> Self::Output {
                if self.0 >= rhs.0 {
                    $n::new(self.0 - rhs.0)
                } else {
                    $n::new($m - rhs.0 + self.0)
                }
            }
        }

        impl std::ops::Mul for $n {
            type Output = $n;
            fn mul(self, rhs: $n) -> Self::Output {
                $n::new(self.0 * rhs.0)
            }
        }

        impl std::ops::Div for $n {
            type Output = $n;
            fn div(self, rhs: $n) -> Self::Output {
                $n::new(self.0 / rhs.0)
            }
        }

        // Assign
        impl std::ops::AddAssign for $n {
            fn add_assign(&mut self, rhs: $n) {
                *self = *self + rhs;
            }
        }

        impl std::ops::SubAssign for $n {
            fn sub_assign(&mut self, rhs: $n) {
                *self = *self - rhs;
            }
        }

        impl std::ops::MulAssign for $n {
            fn mul_assign(&mut self, rhs: $n) {
                *self = *self * rhs;
            }
        }

        impl std::ops::DivAssign for $n {
            fn div_assign(&mut self, rhs: $n) {
                *self = *self / rhs;
            }
        }

        impl std::fmt::Display for $n {
            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                write!(f, "{}", self.0)
            }
        }
        impl std::fmt::Debug for $n {
            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                write!(f, "{}", self.0)
            }
        }
    };
}
// 10^8 < p < 10^9
// 3 is primitive p-1 root of these
// 167772161 = 5*2^25 + 1, 469762049 = 7*2^26 + 1, 998244353 = 119*2^23 + 1
// 1224736769 = 73 * 2^24 + 1
// define_modint!(ModInt167772161, 167772161);
define_modint!(ModInt998244353, 998244353);
define_modint!(ModInt1224736769, 1224736769);
fn ntt<T: ModI>(a: &mut [T], n: usize, inv: bool) {
    // h = log2(n)
    let h = {
        let mut i = 0;
        while 1 << i != n {
            i += 1;
        }
        i
    };
    let mut j: usize;
    for i in 0..n {
        j = 0;
        for k in 0..h {
            // (i >> k & 1)はiのk桁目のbit
            // (h - 1 - k)は全体をh-bitとしてk桁目の反対の位置
            j |= (i >> k & 1) << (h - 1 - k);
        }
        // はじめの一回だけひっくりかえす
        if i < j {
            a.swap(i, j)
        };
    }
    // バタフライ演算
    let mut b = 1;
    while b < n {
        let zeta: T = T::new(3).pow((T::m() - 1) / (2 * b as u64));
        for j in 0..b {
            // 3 is primitive root of proth prime
            // 3 ^ ((m - 1) / (n * j)) is primitive n root's j power
            let e: T = if inv {
                zeta.pow(j as u64).inv()
            } else {
                zeta.pow(j as u64)
            };
            let mut k = 0;
            while k < n {
                let s: T = a[j + k];
                let t: T = a[j + k + b] * e;
                a[j + k] = s + t;
                a[j + k + b] = s - t;
                k += b * 2;
            }
        }
        b *= 2;
    }

    if inv {
        let ni = T::new(n as u64).inv();
        for i in 0..n {
            a[i] *= ni;
        }
    }
}

fn mod_conv<T: ModI>(mut a: &mut [T], mut b: &mut [T]) -> Vec<T> {
    let n = a.len();
    // calc each mod
    ntt(&mut a, n, false);
    ntt(&mut b, n, false);
    let mut c = Vec::with_capacity(n);
    for i in 0..n {
        c.push(a[i] * b[i]);
    }
    ntt(&mut c, n, true);
    c
}

fn single_convolution<T: ModI>(a: &mut [T], b: &mut [T]) -> Vec<T> {
    let d: usize = a.len() + b.len() - 1;
    let n = d.checked_next_power_of_two().unwrap();
    let mut a = a.to_vec();
    a.resize(n, T::new(0));
    let mut b = b.to_vec();
    b.resize(n, T::new(0));
    let mut res = mod_conv(&mut a, &mut b);
    res.truncate(d);
    res
}
fn mod_pow(mut a: u64, mut n: u64, m: u64) -> u64 {
    let mut ret = 1;
    while n > 0 {
        if n & 1 == 1 {
            ret *= a;
            ret %= m;
        }
        a *= a;
        a %= m;
        n >>= 1;
    }
    ret
}
// mod mの体におけるaの逆元
fn mod_inv(a: u64, m: u64) -> u64 {
    mod_pow(a, m - 2, m)
}
fn garner(mr: &mut Vec<(u64, u64)>, m: u64) -> u64 {
    mr.push((m, 0));
    // coef... mixed radixの係数, constants... 前まで求めた係数
    let mut coef: Vec<u64> = vec![1; mr.len()];
    let mut constants: Vec<u64> = vec![0; mr.len()];
    for i in 0..mr.len() - 1 {
        let v: u64 = (mr[i].1 + mr[i].0 - constants[i]) * mod_inv(coef[i], mr[i].0) % mr[i].0;
        for j in i + 1..mr.len() {
            constants[j] += coef[j] * v;
            constants[j] %= mr[j].0;
            coef[j] *= mr[i].0;
            coef[j] %= mr[j].0;
        }
    }
    constants[mr.len() - 1]
}

fn primes_under(n: u64) -> Vec<u64> {
    let mut primes: Vec<u64> = vec![];
    // 素数定理を使え
    // x/ln(x)
    let mut non_primes = std::collections::HashSet::with_capacity(n as usize / 2);
    for i in 2..((n as f64).sqrt() as u64 + 1) {
        if non_primes.contains(&i) {
            continue;
        } else {
            primes.push(i);
            let mut k = 2;
            while i * k <= n {
                non_primes.insert(i * k);
                k += 1;
            }
        }
    }
    for i in ((n as f64).sqrt() as u64 + 1)..n + 1 {
        if non_primes.contains(&i) {
            continue;
        } else {
            primes.push(i);
        }
    }
    primes
}

fn main() {
    input! {
        n:u64,
    }
    let ps = primes_under(n);
    type F0 = ModInt1224736769;
    let mut a: Vec<F0> = vec![F0::new(0); ps[ps.len() - 1] as usize + 1];
    let mut b: Vec<F0> = vec![F0::new(0); 2 * ps[ps.len() - 1] as usize + 1];
    for p in &ps {
        a[*p as usize] = F0::new(1);
        b[*p as usize * 2] = F0::new(1);
    }
    let mut res0 = a.clone();
    let mut res1 = b.clone();
    // all
    res0 = single_convolution(
        &mut single_convolution(&mut res0, &mut a.clone()),
        &mut a.clone(),
    );
    // two
    res1 = single_convolution(&mut res1, &mut a.clone());

    let ps3 = primes_under(3 * n);
    let mut ans = 0;
    for p in &ps3 {
        let i = *p as usize;
        if i < res1.len() {
            ans += (res0[i].0 - 3 * res1[i].0) / 6;
        } else if i < res0.len() {
            ans += res0[i].0 / 6;
        } else {
            break;
        }
    }
    println!("{:?}", ans);
}
0