Submission #65506340

---

Source Code Expand

#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,collections::*,iter::*};
use {proconio::{marker::*,*},rustc_hash::*,itertools::*};
use ac_library::{*,modint::ModIntBase,ModInt998244353 as M};


#[fastout]
fn main(){
    // 3000000

    // let mut cnt=0;
    // for i in 2..3e6 as usize{
    //     cnt+=is_prime(i) as usize;
    //     if cnt>=2e5 as usize{
    //         eprintln!("{i}");
    //         break;
    //     }
    // }

    input!{
        q:usize,
        ab:[(usize,usize);q],
    }

    let max=3000000;
    let mut seg=Segtree::<Additive<usize>>::from(vec![1;max+1]);
    seg.set(0,0);

    for &(a,b) in &ab{
        if !(max<a || seg.get(a)==0){
            // aの倍数を消していく
            for i in 1..{
                if max<i*a{
                    break;
                }
                seg.set(i*a,0);
            }
        }

        let right=seg.max_right(0,|&t|t<=b);
        let left=seg.min_left(right,|&t|t==0);

        println!("{}",left-1);
        
        // if seg.get(a)
        // todo!();
    }
}


fn is_prime(n:usize)->bool{
    if n<=1{
        return false;
    }
    for i in 2..{
        if n<i*i{
            break;
        }
        if n%i==0{
            return false;
        }
    }
    true
}

Submission Info

Judge Result