結果

問題 No.1918 Simple Math ?
ユーザー LyricalMaestro
提出日時 2024-09-09 01:55:32
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,838 bytes
コンパイル時間 15,110 ms
コンパイル使用メモリ 393,512 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-09-09 01:55:56
合計ジャッジ時間 21,746 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 TLE * 1 -- * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
 --> src/main.rs:4:9
  |
4 |     let mut n1 = ((a + 1) / 2) + 1;
  |         ----^^
  |         |
  |         help: remove this `mut`
  |
  = note: `#[warn(unused_mut)]` on by default

warning: variable `N` should have a snake case name
 --> src/main.rs:3:18
  |
3 | fn solve(a: i64, N: i64) -> i64 {
  |                  ^ help: convert the identifier to snake case: `n`
  |
  = note: `#[warn(non_snake_case)]` on by default

warning: variable `T` should have a snake case name
  --> src/main.rs:61:9
   |
61 |     let T: i64 = reader.next().unwrap().unwrap().trim().parse().unwrap();
   |         ^ help: convert the identifier to snake case: `t`

warning: variable `N` should have a snake case name
  --> src/main.rs:68:13
   |
68 |         let N: i64 = iter.next().unwrap().parse().unwrap();
   |             ^ help: convert the identifier to snake case: `n`

ソースコード

diff # 

const MOD: i64 = 1_000_000_007;

fn solve(a: i64, N: i64) -> i64 {
    let mut n1 = ((a + 1) / 2) + 1;
    let mut answer = 0;
    let mut low = 1;
    
    for i in 1..=std::cmp::min(n1, N) {
        let x = a * i;
        let mut high = 1_000_000_000;
        while high - low > 1 {
            let mid = (high + low) / 2;
            if mid * mid <= x {
                low = mid;
            } else {
                high = mid;
            }
        }
        let v = if high * high <= x { high } else { low };
        
        answer = (answer + v) % MOD;
        low = v;
    }
    
    // 最上位から
    low = 0;
    let mut high = 1_000_000_000;
    while high - low > 1 {
        let mid = (high + low) / 2;
        if mid * mid <= a * N {
            low = mid;
        } else {
            high = mid;
        }
    }
    let mut v = if high * high <= a * N { high } else { low };
    
    let mut n0 = N;
    while n1 < n0 {
        let mut x = (v * v) / a;
        if x * a < v * v {
            x += 1;
        }
        x = std::cmp::max(n1 + 1, x);
        
        let y = (n0 - x + 1) % MOD;
        answer = (answer + (y * v) % MOD) % MOD;
        v -= 1;
        n0 = x - 1;
    }
    
    answer
}

fn main() {
    use std::io::{self, BufRead};
    
    let stdin = io::stdin();
    let mut reader = stdin.lock().lines();
    
    let T: i64 = reader.next().unwrap().unwrap().trim().parse().unwrap();
    let mut answers = Vec::new();
    
    for _ in 0..T {
        let line = reader.next().unwrap().unwrap();
        let mut iter = line.split_whitespace();
        let a: i64 = iter.next().unwrap().parse().unwrap();
        let N: i64 = iter.next().unwrap().parse().unwrap();
        let ans = solve(a, N);
        answers.push(ans);
    }
    
    for ans in answers {
        println!("{}", ans);
    }
}
0