結果
| 問題 | No.1661 Sum is Prime (Hard Version) |
| コンテスト | |
| ユーザー |
 koba-e964
|
| 提出日時 | 2021-11-11 11:32:03 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 323 ms / 3,000 ms |
| コード長 | 4,727 bytes |
| 記録 | |
| コンパイル時間 | 1,029 ms |
| コンパイル使用メモリ | 205,588 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-06-04 06:02:14 |
| 合計ジャッジ時間 | 4,972 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 |
コンパイルメッセージ
warning[E0133]: call to unsafe function `core::slice::<impl [T]>::get_unchecked` is unsafe and requires unsafe block
--> src/main.rs:54:24
|
54 | let val = *self.dp_big.get_unchecked(idx as usize);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ call to unsafe function
|
= note: for more information, see <https://doc.rust-lang.org/edition-guide/rust-2024/unsafe-op-in-unsafe-fn.html>
= note: consult the function's documentation for information on how to avoid undefined behavior
note: an unsafe function restricts its caller, but its body is safe by default
--> src/main.rs:50:5
|
50 | unsafe fn upd<F>(&mut self, pos: i64, f: F) where F: Fn(i64) -> i64 {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
= note: `#[warn(unsafe_op_in_unsafe_fn)]` (part of `#[warn(rust_2024_compatibility)]`) on by default
warning[E0133]: call to unsafe function `core::slice::<impl [T]>::get_unchecked_mut` is unsafe and requires unsafe block
--> src/main.rs:55:14
|
55 | *self.dp_big.get_unchecked_mut(idx as usize) = f(val);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ call to unsafe function
|
= note: for more information, see <https://doc.rust-lang.org/edition-guide/rust-2024/unsafe-op-in-unsafe-fn.html>
= note: consult the function's documentation for information on how to avoid undefined behavior
warning[E0133]: call to unsafe function `core::slice::<impl [T]>::get_unchecked` is unsafe and requires unsafe block
--> src/main.rs:59:20
|
59 | let val = *self.dp.get_unchecked(idx);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ call to unsafe function
|
= note: for more information, see <https://doc.rust-lang.org/edition-guide/rust-2024/unsafe-op-in-unsafe-fn.html>
= note: consult the function's documentation for information on how to avoid undefined behavior
warning[E0133]: call to unsafe function `core::slice::<impl [T]>::get_unchecked
ソースコード
use std::cmp::*;
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes.by_ref().map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
macro_rules! input_inner {
($next:expr) => {};
($next:expr,) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
macro_rules! read_value {
($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}
struct DivDP {
// stores dp[n], dp[n/2], ..., dp[n/b].
dp_big: Vec<i64>,
dp: Vec<i64>,
n: i64,
b: i64,
}
impl DivDP {
fn new(n: i64, b: i64) -> Self {
let dp_big = vec![0; b as usize + 1];
let dp = vec![0; (n / b) as usize];
DivDP {
dp_big: dp_big,
dp: dp,
n: n,
b: b,
}
}
// pos should be of form floor(n / ???).
unsafe fn upd<F>(&mut self, pos: i64, f: F) where F: Fn(i64) -> i64 {
if pos >= self.n / self.b {
let idx = self.n / pos;
debug_assert_eq!(pos, self.n / idx);
let val = *self.dp_big.get_unchecked(idx as usize);
*self.dp_big.get_unchecked_mut(idx as usize) = f(val);
return;
}
let idx = pos as usize;
let val = *self.dp.get_unchecked(idx);
*self.dp.get_unchecked_mut(idx) = f(val);
}
unsafe fn get(&self, pos: i64) -> i64 {
if pos >= self.n / self.b {
let idx = self.n / pos;
debug_assert_eq!(pos, self.n / idx);
return *self.dp_big.get_unchecked(idx as usize);
}
let idx = pos as usize;
*self.dp.get_unchecked(idx)
}
fn init<F>(&mut self, f: F) where F: Fn(i64) -> i64 {
for i in 0..self.dp.len() {
self.dp[i] = f(i as i64);
}
for i in (1..self.dp_big.len()).rev() {
self.dp_big[i] = f(self.n / i as i64);
}
}
#[allow(unused)]
fn upd_all<F>(&mut self, f: F) where F: Fn(i64, i64) -> i64 {
for i in 0..self.dp.len() {
self.dp[i] = f(i as i64, self.dp[i]);
}
for i in (1..self.dp_big.len()).rev() {
self.dp_big[i] = f(self.n / i as i64, self.dp_big[i]);
}
}
}
impl std::fmt::Debug for DivDP {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
for i in 0..self.dp.len() {
writeln!(f, "{}: {}", i, self.dp[i])?;
}
for i in (1..self.dp_big.len()).rev() {
writeln!(f, "{}: {}", self.n / i as i64, self.dp_big[i])?;
}
Ok(())
}
}
fn primes(v: usize) -> Vec<usize> {
let mut pr = vec![true; v + 1];
pr[0] = false;
pr[1] = false;
for i in 2..v + 1 {
if !pr[i] {
continue;
}
for j in 2..v / i + 1 {
pr[i * j] = false;
}
}
let prs: Vec<_> = (0..v + 1).filter(|&i| pr[i]).collect();
prs
}
fn is_prime(x: i64) -> bool {
if x <= 1 {
return false;
}
let mut i = 2;
while i * i <= x {
if x % i == 0 {
return false;
}
i += 1;
}
true
}
// return pi(n) + pi(n / 2)
fn calc(n: i64, prs: &[usize]) -> i64 {
if n <= 1 {
return 0;
}
let mut sqn = 0;
while sqn * sqn <= n {
sqn += 1;
}
sqn -= 1;
let mut dp = DivDP::new(n, sqn);
dp.init(|x| max(0, x - 1));
unsafe {
for &p in prs {
let p = p as i64;
if p * p > n {
break;
}
for i in 1..=min(sqn, n / p / p) {
let val = dp.get(n / i / p);
let val = val - dp.get(p - 1);
dp.upd(n / i, |x| x - val);
}
for i in (p * p..n / sqn).rev() {
let val = dp.get(i / p);
let val = val - dp.get(p - 1);
dp.upd(i, |x| x - val);
}
}
// dp[j] = #{x <= j | x is prime}
dp.get(n) + dp.get(n / 2)
}
}
// Tags: lucys-algorithm, prime-counting
fn main() {
input!(l: i64, r: i64);
let prs = primes(150_000);
let mut val = calc(2 * r - 1, &prs) - calc(2 * l - 1, &prs);
if is_prime(r) {
val += 1;
}
if 2 * l - 1 < 2 && 2 <= 2 * r - 1 {
val -= 1;
}
println!("{}", val);
}