結果
問題 | No.1322 Totient Bound |
ユーザー |
![]() |
提出日時 | 2021-12-11 01:43:44 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 273 ms / 5,000 ms |
コード長 | 7,219 bytes |
コンパイル時間 | 15,393 ms |
コンパイル使用メモリ | 377,048 KB |
実行使用メモリ | 7,680 KB |
最終ジャッジ日時 | 2024-07-19 00:57:46 |
合計ジャッジ時間 | 21,443 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
// ---------- begin miller-rabin ----------fn is_prime_miller(n: u64) -> bool {if n <= 1 {return false;} else if n <= 3 {return true;} else if n % 2 == 0 {return false;}let pow = |r: u64, mut m: u64| -> u64 {let mut t = 1u128;let mut s = (r % n) as u128;let n = n as u128;while m > 0 {if m & 1 == 1 {t = t * s % n;}s = s * s % n;m >>= 1;}t as u64};let mut d = n - 1;let mut s = 0;while d % 2 == 0 {d /= 2;s += 1;}const B: [u64; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];for &b in B.iter() {let mut a = pow(b, d);if a <= 1 {continue;}let mut i = 0;while i < s && a != n - 1 {i += 1;a = (a as u128 * a as u128 % n as u128) as u64;}if i >= s {return false;}}true}// ---------- end miller-rabin ----------// 初期化配列// 初期値とサイズを与えて適当にやる系// new(size, zero): zero埋めした長さsizeの配列を返す// init(&mut self): 初期化// index(mut) でアクセスしたときその履歴を溜め込む// それ以外でアクセスすると死ぬので注意//// 考えるべきこと// 1. deref で dataへアクセスできるようにしていいか// derefmut はダメ// 2. 今のままだと二次元配列の初期化とかには対応できない// なんか方法を考えたい// ---------- begin init array ----------#[derive(Clone)]pub struct InitArray<T> {data: Vec<T>,used: Vec<bool>,list: Vec<u32>,zero: T,}impl<T: Copy> InitArray<T> {pub fn new(zero: T, size: usize) -> Self {InitArray {data: vec![zero; size],used: vec![false; size],list: vec![],zero: zero,}}pub fn init(&mut self) {self.init_with(|_, _| ());}pub fn init_with<F>(&mut self, mut f: F)whereF: FnMut(usize, T),{for x in self.list.drain(..) {let x = x as usize;self.used[x] = false;let v = std::mem::replace(&mut self.data[x], self.zero);f(x, v);}}}impl<T> std::ops::Index<usize> for InitArray<T> {type Output = T;fn index(&self, pos: usize) -> &Self::Output {&self.data[pos]}}impl<T> std::ops::IndexMut<usize> for InitArray<T> {fn index_mut(&mut self, pos: usize) -> &mut Self::Output {if !self.used[pos] {self.used[pos] = true;self.list.push(pos as u32);}&mut self.data[pos]}}// ---------- end init array ----------// ---------- begin prime count ----------// 処理が終わった時// large[i]: pi(floor(n / i))// small[i]: pi(i)// となっている// O(N^(3/4)/log N)pub fn prime_count(n: usize) -> (Vec<usize>, Vec<usize>) {if n <= 1 {return (vec![0, 0], vec![0, 0]);}let sqrt = (1..).find(|p| p * p > n).unwrap() - 1;let mut large = vec![0; sqrt + 1];let mut small = vec![0; sqrt + 1];for (i, (large, small)) in large.iter_mut().zip(&mut small).enumerate().skip(1) {*large = n / i - 1;*small = i - 1;}for p in 2..=sqrt {if small[p] == small[p - 1] {continue;}let pi = small[p] - 1;let q = p * p;for i in 1..=sqrt.min(n / q) {large[i] -= *large.get(i * p).unwrap_or_else(|| &small[n / (i * p)]) - pi;}for i in (q..=sqrt).rev() {small[i] -= small[i / p] - pi;}}(small, large)}// ---------- end prime count ----------// ---------- begin enumerate prime ----------fn enumerate_prime<F>(n: usize, mut f: F)whereF: FnMut(usize),{assert!(1 <= n && n <= 5 * 10usize.pow(8));let batch = (n as f64).sqrt().ceil() as usize;let mut is_prime = vec![true; batch + 1];for i in (2..).take_while(|p| p * p <= batch) {if is_prime[i] {let mut j = i * i;while let Some(p) = is_prime.get_mut(j) {*p = false;j += i;}}}let mut prime = vec![];for (i, p) in is_prime.iter().enumerate().skip(2) {if *p && i <= n {f(i);prime.push(i);}}let mut l = batch + 1;while l <= n {let r = std::cmp::min(l + batch, n + 1);is_prime.clear();is_prime.resize(r - l, true);for &p in prime.iter() {let mut j = (l + p - 1) / p * p - l;while let Some(is_prime) = is_prime.get_mut(j) {*is_prime = false;j += p;}}for (i, _) in is_prime.iter().enumerate().filter(|p| *p.1) {f(i + l);}l += batch;}}// ---------- end enumerate prime ----------fn read() -> usize {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();s.trim().parse().unwrap()}fn solve(n: usize) {let sqrt = (2..).find(|p| p * p > n).unwrap() - 1;let mut pi = prime_count(n);for i in 1..=sqrt {if is_prime_miller(i as u64 + 1) {pi.0[i] += 1;}if is_prime_miller((n / i) as u64 + 1) {pi.1[i] += 1;}}let pi = |x: usize| -> usize {let x = x - 1;if x < pi.0.len() {pi.0[x]} else {pi.1[n / x]}};let mut prime = vec![];enumerate_prime(sqrt + 100000, |p| prime.push(p));let mut large = InitArray::new(0, sqrt + 1);let mut small = InitArray::new(0, sqrt + 1);let mut next_large = InitArray::new(0, sqrt + 1);let mut next_small = InitArray::new(0, sqrt + 1);large[1] = 1usize;let mut ans = 0;for (i, &p) in prime.iter().enumerate() {let mut prun = |m: usize, v: usize| -> bool {(p - 1) * p > m && {ans += v;if p <= m + 1 {ans += v * (pi(m + 1) - i);}true}};large.init_with(|d, v| {let m = n / d;if prun(m, v) {return;}next_large[d] += v;let mut d = d * (p - 1);while d <= sqrt {next_large[d] += v;d *= p;}let mut m = n / d;while m > 0 {next_small[m] += v;m /= p;}});small.init_with(|m, v| {if prun(m, v) {return;}next_small[m] += v;let mut m = m / (p - 1);while m > 0 {next_small[m] += v;m /= p;}});std::mem::swap(&mut small, &mut next_small);std::mem::swap(&mut large, &mut next_large);}println!("{}", ans);}fn main() {solve(read());}