// 愚直解との折衷で検算(2つ前の提出はミス、1つ前の提出はO(min(M,N))じゃなくてO(M)) #include using namespace std; using ll = long long; #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT int main() { UNTIE; constexpr const ll bound = 1000000000; CIN_ASSERT( N , 1 , bound ); CIN_ASSERT( M , 1 , bound ); // sum( ll i = 1 ; i <= N ; i++ ) sum( ll j = 1 ; j <= M ; j++ ){ i % j } // = sum( ll j = 1 ; j <= M ; j++ ) sum( ll i = 1 ; i <= N ; i++ ){ i % j } // = sum( ll j = 1 ; j <= M ; j++ ){ ( N / j ) * ( ( j - 1 ) * j ) / 2 + ( N % j ) * ( N % j + 1 ) / 2 } constexpr const ll P = 998244353; if( M < 100000000 ){ ll answer0 = 0; ll answer1 = 0; ll N_r; ll j_sum = 0; FOREQ( j , 1 , M ){ N_r = N % j; j_sum = ( j_sum + j - 1 ) % P; answer0 += ( ( N / j ) * j_sum ) % P; answer1 += ( N_r * ( N_r + 1 ) ) % P; } answer1 = ( answer1 % P ) * ( ( P + 1 ) / 2 ); RETURN( ( answer0 + answer1 ) % P ); } // sum( ll i = 1 ; i <= N ; i++ ) sum( ll j = 1 ; j <= M ; j++ ){ i % j } // = sum( ll i = 1 ; i <= N ; i++ ) sum( ll j = 1 ; j <= M ; j++ ){ i - ( i / j ) * j } // = M * sum( ll i = 1 ; i <= N ; i++ ){ i } // - sum( ll i = 1 ; i <= N ; i++ ) sum( ll j = 1 ; j <= M ; j++ ){ ( i / j ) * j } // = M * ( N * ( N + 1 ) ) / 2 // - sum( ll j = 1 ; j <= M ; j++ ){ j * sum( ll i = 1 ; i <= N ; i++ ){ i / j } } // = M * ( N * ( N + 1 ) ) / 2 // - sum( ll j = 1 ; j <= M ; j++ ){ j * ( j * ( ( N / j - 1 ) * ( N / j ) ) / 2 + ( N - j * ( N / j ) + 1 ) * ( N / j ) ) } // = M * ( N * ( N + 1 ) ) / 2 // - sum( ll j = 1 ; j <= M ; j++ ){ j ^ 2 * ( ( ( N / j - 1 ) * ( N / j ) ) / 2 - ( N / j ) ^ 2 ) + j * ( N + 1 ) * ( N / j ) } // = M * ( N * ( N + 1 ) ) / 2 // - sum( ll j = 1 ; j <= M ; j++ ){ j * ( N + 1 ) * ( N / j ) - j ^ 2 * ( ( ( N / j ) * ( N / j + 1 ) ) / 2 ) } // = M * ( N * ( N + 1 ) ) / 2 // - sum( ll j = 1 ; j <= min( N / ( N / 31622 ) - 1 , M ) ; j++ ){ j * ( N + 1 ) * ( N / j ) - j ^ 2 * ( ( ( N / j ) * ( N / j + 1 ) ) / 2 ) } // - sum( ll j = N / ( N / 31622 ) ; j <= M ; j++ ){ j * ( N + 1 ) * ( N / j ) - j ^ 2 * ( ( ( N / j ) * ( N / j + 1 ) ) / 2 ) } ll answer0 = ( M * ( ( ( N * ( N + 1 ) ) / 2 ) % P ) ) % P; ll answer1 = 0; ll answer2 = 0; ll answer3 = 0; constexpr const ll sqrt_bound = 31622; ll h = N / sqrt_bound; // N / j > h // <=> N / j >= h + 1 // <=> N / ( 1.0 * j ) >= h + 1 // <=> N >= ( h + 1 ) * j // <=> N / ( h + 1 ) >= j ll border = N / ( h + 1 ); if( M > N ){ M = N; } if( border > M ){ border = M; } FOREQ( j , 1 , border ){ answer1 += ( j * ( ( N + 1 ) * ( N / j ) - j * ( ( ( N / j ) * ( N / j + 1 ) ) / 2 ) ) ) % P; } answer1 %= P; ll j_prev = border; ll j_curr = ( h > 0 ? N / h : N + 1 ); ll sum_prev = j_prev * ( j_prev + 1 ); ll sum_curr; ll square_sum_prev = ( j_prev * ( j_prev + 1 ) * ( 2 * j_prev + 1 ) ) % P; ll square_sum_curr; while( j_curr <= M ){ sum_curr = j_curr * ( j_curr + 1 ); square_sum_curr = ( j_curr * ( ( ( j_curr + 1 ) * ( 2 * j_curr + 1 ) ) % P ) ) % P; answer2 += ( ( ( sum_curr - sum_prev ) % P ) * h ) % P; answer3 += ( ( ( ( ( square_sum_curr + P - square_sum_prev ) % P ) * h ) % P ) * ( h + 1 ) ) % P; j_prev = j_curr; sum_prev = sum_curr; square_sum_prev = square_sum_curr; // h = N / j // <=> N / ( i.0 * j ) - 1 < h <= N / ( 1.0 * j ) // <=> N - j < h * j <= N // <=> h * j <= N < ( h + 1 ) * j // <=> N / ( 1.0 * ( h + 1 ) ) < j <= N / ( 1.0 * h ) // <=> N / ( 1.0 * ( h + 1 ) ) < j <= N / h // exists j[ h = N / j ] // <=> N / ( 1.0 * ( h + 1 ) ) < N / h // <=> N < ( N / h ) * ( h + 1 ) if( h > 1 && j_curr < M ){ h--; j_curr = N / h ; while( N >= j_curr * ( h + 1 ) ){ h--; j_curr = N / h ; } if( j_curr > M ){ j_curr = M; } } else { break; } } constexpr const ll inv_2 = ( P + 1 ) / 2; constexpr const ll inv_3 = P - ( ( P / 3 ) * inv_2 ) % P; constexpr const ll inv_12 = ( ( ( inv_2 * inv_2 ) % P ) * inv_3 ) % P; answer2 = ( ( ( ( N + 1 ) * ( answer2 % P ) ) % P ) * inv_2 ) % P; answer3 = ( ( answer3 % P ) * inv_12 ) % P; RETURN( ( answer0 + ( P - answer1 ) + ( P - answer2 ) + answer3 ) % P ); }