結果
問題 | No.1276 3枚のカード |
ユーザー |
![]() |
提出日時 | 2022-02-26 14:45:27 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,928 bytes |
コンパイル時間 | 11,678 ms |
コンパイル使用メモリ | 378,292 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-07-04 10:55:26 |
合計ジャッジ時間 | 15,591 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
fn quot_range<F>(n: u32, mut f: F)whereF: FnMut(u32, u32, u32){let mut pre = (0, 0);for d in 1.. {let q = n / d;if pre != (0, 0) {let (q, l, r) = (pre.0, q + 1, pre.1);f(l, r, q);}if q < d {break;}pre = (d, q);f(d, d, q);if q == d {break;}}}fn read() -> u32 {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();s.trim().parse().unwrap()}fn main() {let n = read();const MOD: u64 = 1_000_000_007;let mut ans = 0;quot_range(n, |l, r, q| {let l = l as u64;let r = r as u64;let q = q as u64;let n = n as u64;ans += (r - l + 1) * (q - 1) * (n - 2) % MOD;ans += MOD - (r - l + 1) * (q - 1) * (q - 2) % MOD;});let k = (n as f64 / (n as f64).ln_1p().ln_1p().max(1f64)).cbrt().powi(2) as u32;let mut memo = vec![0; k as usize + 1];for b in 2..=k {for c in 2..=(k / b) {let v = (c - 1) as u64;memo[(b * c) as usize] += v;memo.get_mut((b * (c + 1)) as usize).map(|p| *p += MOD - v);}let x = b as usize;memo[x] = (memo[x] + memo[x - 1]) % MOD;}let mut large = vec![0; 1 + (n / k) as usize];for i in (1..=(n / k)).rev() {let m = n / i;quot_range(m, |l, r, q| {if l > 1 {large[i as usize] += (r - l + 1) as u64 * (q - 1) as u64;}});large[i as usize] %= MOD;}quot_range(n, |l, r, q| {if q <= 2 {return;}let w = (r - l + 1) as u64;let s = if q <= k {memo[q as usize]} else {large[(n / q) as usize]};ans += MOD - s * w % MOD;});ans %= MOD;println!("{}", ans);}