AtCoder: B - Between a and b ... - 파이썬(Python)

https://atcoder.jp/contests/abc048/tasks/abc048_b

B - Between a and b ...

<문제 선지>

음이 아닌 정수 a와 b(a≤b)와 양의 정수 x가 있다고 하자. a와 b 사이의 정수 중에서 x로 나누어 떨어지는 정수는 몇 개인가?

 

<접근 방법>

a와 b 사이의 x의 배수의 개수를 찾는 문제이다. 단순히 for문을 이용하면 TLE가 발생할 것이다. 왜냐하면 a, b의 최대 범위는 $10^{18}$이 될 수 있고 해당 범위는 제한 시간인 2초 내로 실행할 수 없기 때문이다.

 

그렇다면 어떤 방법을 이용해야 할까? 우선, 1부터 a까지의 범위에서 x의 배수의 개수를 구하는 방법을 찾아보자.

예시 상황을 가정해보자. $a = 10, x = 3$이라고 해보자. 그러면 1부터 10까지 존재하는 3의 배수는 다음과 같을 것이다.

number	1	2	3	4	5	6	7	8	9	10
3의 배수	X	X	O	X	X	O	X	X	O	X

 

즉, 3, 6, 9로 총 3개가 된다는 것을 알 수 있다. 결과적으로 $floor(a / x)$로 계산할 수 있다.

 

그러면 확장하여 a에서 b까지에서 x의 배수의 개수를 계산하는 방법을 찾아보자. 아래의 식을 이용하면 a에서 b까지의 x의 배수의 개수를 계산할 수 있을 것이다.

 

$$(1에서 b까지에서 x의 배수의 개수) - (1에서 a까지에서 x의 배수의 개수)$$

 

왜냐하면, 1에서 b까지의 범위에는 1부터 a까지의 범위가 포함되어 있다. 그러면 a에서 b까지의 범위를 계산하는 방법으로 위의 식을 사용할 수 있기 때문이다.

 

해당 방법을 적용하면 for문을 사용하는 $O(n)$ 보다 더 빠른 $O(1)$으로 처리할 수 있다.

 

<소스 코드>

위의 접근법을 구현한 전체 소스 코드이다.

여기서 주의해야 할 사항이 있다. a가 x의 배수인지를 확인해야 한다. 위의 식을 적용하면 a 값이 제외될 수 있기 때문이다.

a, b, x = map(int, input().split())
res = 0
if a % x == 0:
    res += 1
res += b // x - a // x
print(res)