Divisible Sum Difference

Easy

0/40

0 upvote

Problem statement

You are given two positive integers, n and m. Your task is to find the sum of all integers in the range from 1 to m (inclusive) that are divisible by n, and the sum of all integers in the same range that are not divisible by n.

Let sum_divisible be the sum of numbers from 1 to m that are divisible by n.

Let sumnotdivisible be the sum of numbers from 1 to m that are not divisible by n.

You must calculate and return the difference: sumnotdivisible - sum_divisible.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line of input contains two space-separated integers, n and m.

Output Format:

Print a single integer representing the calculated difference.

Note:

A brute-force loop that iterates from 1 to m will be too slow for the given constraints. The problem can be solved in O(1) time by using mathematical formulas for arithmetic series. The sums can become very large, so be sure to use a 64-bit integer type (like long in Java or long long in C++) for your calculations.

Sample Input 1:

4 20

Sample Output 1:

Explanation for Sample 1:

Sum of numbers divisible by 4 (from 1 to 20): 4 + 8 + 12 + 16 + 20 = 60.
Sum of numbers not divisible by 4 (from 1 to 20): 1 + 2 + 3 + 5 + ... + 19 = 150.
The required difference is 150 - 60 = 90.

Sample Input 2:

3 10

Sample Output 2:

Explanation for Sample 2:

Sum of numbers divisible by 3 (from 1 to 10): 3 + 6 + 9 = 18.
Sum of numbers not divisible by 3 (from 1 to 10): 1 + 2 + 4 + 5 + 7 + 8 + 10 = 37.
The required difference is 37 - 18 = 19.

Expected Time Complexity:

The expected time complexity is O(1).

Constraints:

1 <= n, m <= 10^12

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Divisible Sum Difference

Console