Yet Another Counting Problem (Codeforces 1342C)
Tags: Math, number theory

You are given two integers $$$a$$$ and $$$b$$$, and $$$q$$$ queries. The $$$i$$$-th query consists of two numbers $$$l_i$$$ and $$$r_i$$$, and the answer to it is the number of integers $$$x$$$ such that $$$l_i \le x \le r_i$$$, and $$$((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a)$$$. Calculate the answer for each query.Recall that $$$y \bmod z$$$ is the remainder of the division of $$$y$$$ by $$$z$$$. For example, $$$5 \bmod 3 = 2$$$, $$$7 \bmod 8 = 7$$$, $$$9 \bmod 4 = 1$$$, $$$9 \bmod 9 = 0$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then the test cases follow.The first line of each test case contains three integers $$$a$$$, $$$b$$$ and $$$q$$$ ($$$1 \le a, b \le 200$$$; $$$1 \le q \le 500$$$).Then $$$q$$$ lines follow, each containing two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{18}$$$) for the corresponding query.

Output: For each test case, print $$$q$$$ integers — the answers to the queries of this test case in the order they appear.


Sample Inputs:
2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200

Sample Outputs:
0 0 0 2 4 
0 91

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()
import math

def solve():
    (a, b, q) = readInts()
    if a < b:
        (b, a) = (a, b)
    lcm = a * b // math.gcd(a, b)
    res = []
    for _ in range(q):
        (L, R) = readInts()
        if a == b:
            res.append(0)
        elif a % b == 0:
            res.append(0)
        else:
            ans = R - L + 1
            cnt = R // lcm - (L - 1) // lcm
            rm = R % lcm
            if cnt:
                ans -= min(rm + 1, a)
            ans -= max(cnt - 1, 0) * a
            if L <= lcm * ((L - 1) // lcm) + (a - 1):
                ans -= min(lcm * ((L - 1) // lcm) + (a - 1) - L + 1, R - L + 1)
            res.append(ans)
    print(*res)
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()
import math

def solve():
    (a, b, q) = readInts()
    if a < b:
        (b, a) = (a, b)
    lcm = a * b // math.gcd(a, b)
    res = []
    for _ in range(q):
        (L, R) = readInts()
        if a == b:
            res.append(0)
        elif a % b == 0:
            res.append(0)
        else:
            ans = R - L + 1
            (cnt, rm) = (R // lcm - (L - 1) // lcm, R % lcm)
            if cnt:
                ans -= min(rm + 1, a)
            ans -= max(cnt - 1, 0) * a + max(min(lcm * ((L - 1) // lcm) + (a - 1) - L + 1, R - L + 1), 0)
            res.append(ans)
    print(*res)
for _ in range(int(input())):
    solve()

Solution (Python):
from sys import stdin
input = stdin.readline

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

def solve(l, r):
    value = r // x - (l - 1) // x
    upper = min(r + 1, x * ((l - 1) // x) + b)
    sub = max(0, upper - l)
    if value == 0:
        return r - l + 1 - sub
    sub += (value - 1) * b
    sub += min(r % x + 1, b)
    return r - l + 1 - sub

def answer():
    for query in range(q):
        (l, r) = map(int, input().split())
        print(solve(l, r), end=' ')
for T in range(int(input())):
    (a, b, q) = map(int, input().split())
    (a, b) = (min(a, b), max(a, b))
    x = lcm(a, b)
    answer()
    print()