#1020415 (Rust) No.2940 Sigma Sigma Div Floor Problem

提出ソース

結果

問題	No.2940 Sigma Sigma Div Floor Problem
ユーザー	CoCo_Japan_pan
提出日時	2024-10-18 21:35:28
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	20 ms / 6,000 ms
コード長	9,669 bytes
コンパイル時間	16,448 ms
コンパイル使用メモリ	404,880 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-10-18 22:26:07
合計ジャッジ時間	16,210 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,820 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	1 ms 6,820 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	0 ms 6,820 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	1 ms 6,820 KB
testcase_07	AC	1 ms 6,816 KB
testcase_08	AC	1 ms 6,816 KB
testcase_09	AC	1 ms 6,816 KB
testcase_10	AC	1 ms 6,816 KB
testcase_11	AC	1 ms 6,816 KB
testcase_12	AC	1 ms 6,820 KB
testcase_13	AC	1 ms 6,820 KB
testcase_14	AC	1 ms 6,816 KB
testcase_15	AC	1 ms 6,816 KB
testcase_16	AC	1 ms 6,816 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	14 ms 6,816 KB
testcase_19	AC	11 ms 6,820 KB
testcase_20	AC	11 ms 6,816 KB
testcase_21	AC	19 ms 6,820 KB
testcase_22	AC	4 ms 6,816 KB
testcase_23	AC	5 ms 6,820 KB
testcase_24	AC	9 ms 6,820 KB
testcase_25	AC	10 ms 6,816 KB
testcase_26	AC	13 ms 6,816 KB
testcase_27	AC	2 ms 6,816 KB
testcase_28	AC	20 ms 6,820 KB
testcase_29	AC	19 ms 6,816 KB
testcase_30	AC	2 ms 6,816 KB
testcase_31	AC	5 ms 6,816 KB
testcase_32	AC	2 ms 6,816 KB
08_evil_01.txt	WA	-
08_evil_02.txt	WA	-
08_evil_03.txt	WA	-
08_evil_04.txt	WA	-
08_evil_05.txt	WA	-
08_evil_06.txt	WA	-
08_evil_07.txt	WA	-
08_evil_08.txt	WA	-
08_evil_09.txt	WA	-
08_evil_10.txt	WA	-
08_evil_11.txt	WA	-
08_evil_12.txt	WA	-
08_evil_13.txt	WA	-
08_evil_14.txt	WA	-
08_evil_15.txt	WA	-
08_evil_16.txt	WA	-
08_evil_17.txt	WA	-
08_evil_18.txt	WA	-
08_evil_19.txt	WA	-
08_evil_20.txt	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#![allow(unused_imports, non_snake_case)]
pub use __cargo_equip::prelude::*;

use proconio::{marker::*, *};
use static_modint::ModInt998244353 as MInt;

#[fastout]
fn main() {
    input! {
        N: usize,
    }
    if N > 1_200_000 {
        return;
    }
    let mut ans = MInt::new(0);
    let two_inv = MInt::new(2).inv();
    for j in 1..=N {
        // j*(1+2+...N/j-1) + N/j*(0..=余り)
        let nj = MInt::new(N / j);
        ans += (nj - 1) * nj * two_inv * j;
        ans += nj * (N % j + 1);
    }
    println!("{}", ans);
}

#[macro_export]
macro_rules! mat {
    ($($e:expr),*) => { vec![$($e),*] };
    ($($e:expr,)*) => { vec![$($e),*] };
    ($e:expr; $d:expr) => { vec![$e; $d] };
    ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

#[macro_export]
macro_rules! chmin {
    ($a:expr, $b:expr) => {
        if $a > $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

#[macro_export]
macro_rules! chmax {
    ($a:expr, $b:expr) => {
        if $a < $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

/// https://maguro.dev/debug-macro/
#[macro_export]
macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
    };
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `internal_modint 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#66340933fd234b82f0daf7788b70bbaea1a40f5f)`      licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_modint_0_1_0`
///  - `internal_type_traits 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#66340933fd234b82f0daf7788b70bbaea1a40f5f)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
///  - `static_modint 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#66340933fd234b82f0daf7788b70bbaea1a40f5f)`        licensed under `CC0-1.0` as `crate::__cargo_equip::crates::static_modint`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __internal_modint_0_1_0 {use crate::__cargo_equip::preludes::__internal_modint_0_1_0::*;use internal_type_traits::{One,Zero};use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;pub trait ModInt:Debug+Default+Clone+PartialEq+Eq+Display+Copy+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+Neg<Output=Self>+FromStr+Zero+One{fn new<T:RemEuclidU32>(x:T)->Self;fn raw(x:u32)->Self;fn value(&self)->u32;fn modulus()->u32;fn pow(&self,mut n:u64)->Self{let mut ret=Self::new(1);let mut base=*self;while n>0{if n&1==1{ret*=base;}base*=base;n>>=1;}ret}#[inline]fn inv(&self)->Self{let(g,x)=inv_gcd(self.value()as i64,Self::modulus()as i64);assert_eq!(g,1);Self::raw(x as u32)}}pub const fn safe_mod(mut x:i64,m:i64)->i64{x%=m;if x<0{x+=m;}x}pub const fn inv_gcd(a:i64,b:i64)->(i64,i64){let a=safe_mod(a,b);if a==0{return(b,0);}let mut s=b;let mut t=a;let mut m0=0;let mut m1=1;while t!=0{let u=s/t;s-=t*u;m0-=m1*u;let tmp=s;s=t;t=tmp;let tmp=m0;m0=m1;m1=tmp;}if m0<0{m0+=b/s;}(s,m0)}pub trait RemEuclidU32:Copy{fn rem_euclid_u32(self,modulus:u32)->u32;}impl RemEuclidU32 for u8{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u16{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u32{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self%modulus}}impl RemEuclidU32 for u64{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u64)as u32}}impl RemEuclidU32 for usize{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{let casted:u64=self.try_into().unwrap();casted.rem_euclid_u32(modulus)}}impl RemEuclidU32 for u128{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u128)as u32}}#[inline]fn neg(val:u32,modulus:u32)->u32{if val==0{0}else{modulus-val}}macro_rules!impl_rem_euclid_u32_for_signed{($($t:ty),*)=>{$(impl RemEuclidU32 for$t{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{if self<0{neg(self.unsigned_abs().rem_euclid_u32(modulus),modulus)}else{self.unsigned_abs().rem_euclid_u32(modulus)}}})*};}impl_rem_euclid_u32_for_signed!(i8,i16,i32,i64,isize,i128);macro_rules!impl_rem_for_borrow{($($t:ty),*)=>{$(impl RemEuclidU32 for&$t{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(*self).rem_euclid_u32(modulus)}})*};}impl_rem_for_borrow!(u8,u16,u32,u64,usize,u128,i8,i16,i32,i64,isize,i128);}
        pub mod __internal_type_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add<Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove+Display+Debug{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}
        pub mod static_modint {use crate::__cargo_equip::preludes::static_modint::*;use internal_modint::{ModInt,RemEuclidU32};use internal_type_traits::{One,Zero};use std::fmt::{Debug,Display};use std::iter::{Product,Sum};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;pub type ModInt998244353=StaticModInt<998244353>;pub type ModInt1000000007=StaticModInt<1000000007>;#[derive(Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct StaticModInt<const MOD:u32>{value:u32,}impl<const MOD:u32>Zero for StaticModInt<MOD>{fn zero()->Self{Self::raw(0)}}impl<const MOD:u32>One for StaticModInt<MOD>{fn one()->Self{Self::new(1)}}impl<const MOD:u32>Debug for StaticModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<const MOD:u32>Display for StaticModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<const MOD:u32,T>Sum<T>for StaticModInt<MOD>where Self:Add<T,Output=Self>,{fn sum<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::raw(0),Add::add)}}impl<const MOD:u32,T>Product<T>for StaticModInt<MOD>where Self:Mul<T,Output=Self>,{fn product<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::new(1),Mul::mul)}}impl<const MOD:u32>FromStr for StaticModInt<MOD>{type Err=<i64 as FromStr>::Err;fn from_str(s:&str)->Result<Self,Self::Err>{i64::from_str(s).map(Self::new)}}impl<const MOD:u32>StaticModInt<MOD>{#[inline]pub fn value(&self)->u32{self.value}#[inline]pub fn modulus()->u32{MOD}#[inline]pub fn new<T:RemEuclidU32>(x:T)->Self{ModInt::new(x)}#[inline]pub fn raw(x:u32)->Self{Self{value:x}}#[inline]pub fn pow(&self,n:u64)->Self{ModInt::pow(self,n)}#[inline]pub fn inv(&self)->Self{ModInt::inv(self)}}impl<const MOD:u32>ModInt for StaticModInt<MOD>{#[inline]fn value(&self)->u32{self.value}#[inline]fn modulus()->u32{MOD}#[inline]fn raw(x:u32)->Self{Self{value:x}}#[inline]fn new<T:RemEuclidU32>(x:T)->Self{Self{value:x.rem_euclid_u32(MOD),}}}impl<const MOD:u32>Neg for StaticModInt<MOD>{type Output=Self;#[inline]fn neg(self)->Self{if self.value==0{Self{value:0}}else{Self{value:MOD-self.value,}}}}macro_rules!impl_ops{($trait:ident,$method:ident,$assign_trait:ident,$assign_method:ident)=>{impl<const MOD:u32,T>$trait<T>for StaticModInt<MOD>where Self:$assign_trait<T>,{type Output=Self;fn$method(mut self,rhs:T)->Self{StaticModInt::<MOD>::$assign_method(&mut self,rhs);self}}impl<const MOD:u32,T:RemEuclidU32>$assign_trait<T>for StaticModInt<MOD>{fn$assign_method(&mut self,rhs:T){StaticModInt::<MOD>::$assign_method(self,Self::new(rhs));}}};}impl_ops!(Add,add,AddAssign,add_assign);impl_ops!(Sub,sub,SubAssign,sub_assign);impl_ops!(Mul,mul,MulAssign,mul_assign);impl_ops!(Div,div,DivAssign,div_assign);impl<const MOD:u32>AddAssign for StaticModInt<MOD>{fn add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=MOD{self.value-=MOD;}}}impl<const MOD:u32>SubAssign for StaticModInt<MOD>{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=MOD;}self.value-=rhs.value;}}impl<const MOD:u32>MulAssign for StaticModInt<MOD>{fn mul_assign(&mut self,rhs:Self){self.value=(self.value as u64*rhs.value as u64).rem_euclid_u32(MOD);}}#[allow(clippy::suspicious_op_assign_impl)]impl<const MOD:u32>DivAssign for StaticModInt<MOD>{fn div_assign(&mut self,rhs:Self){*self*=rhs.inv();}}macro_rules!impl_from_primitive{($($t:ty),*)=>{$(impl<const MOD:u32>From<$t>for StaticModInt<MOD>{fn from(x:$t)->Self{Self::new(x)}})*};}impl_from_primitive!(u8,u16,u32,u64,usize,u128,i8,i16,i32,i64,isize,i128);}
    }

    pub(crate) mod macros {
        pub mod __internal_modint_0_1_0 {}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod static_modint {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod __internal_modint_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__internal_type_traits_0_1_0 as internal_type_traits;}
        pub mod __internal_type_traits_0_1_0 {}
        pub mod static_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__internal_modint_0_1_0 as internal_modint,__internal_type_traits_0_1_0 as internal_type_traits};}
    }
}

yukicoder

結果

テストケース

ソースコード