Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、4問目を解説していきたいと思います。
問題名 【B – Between a and b …】
入力
a : 非負の整数
b : 非負の整数
x : 正の整数
考察
制約を見なかったら、aからbまでの間で、xで割り切れる個数を数えれば良さそうです。
cnt = 0
for i in range(a,b+1):
if i % x == 0:
cnt += 1
print(cnt)しかし今回、制約がa <= b <= 10**18なので、最大で、10**18回for文を回さなければならなくて、TLEしてしまいます。なので、別の方法を考えなければなりません。
今回、xで割り切れる個数を求めるので、今一度割り算について考えます。
割り算って
ある数cをxで割るとき、出てくる商とあまりをそれぞれpとqとします。
このとき、pとqというのは、「cという数の中に、xがp個分とq入る」ということです。
もっと言うなら、0からcまでの間で、xの倍数がp個あったということです。
なので、a-bの間にあるxの倍数というのは、0からbまでにあるxの倍数(p1とする) から 0からa未満までにあるxの倍数(p2とする)を引けば求めることができます。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
a,b,x = MI()
l = (a-1)//x
#0からa未満の中で、xの倍数の個数
r = b//x
#0からb以下の中で、xの倍数の個数
print(r-l)まとめ
今回の問題のように、制約次第で難易度が変わるのが、競技プログラミングの面白いところですよね！
前の問題【A – Range Flip Find Route】
次の問題【D – Powerful Discount Tickets】
コメント