Josuke and Complete Graph (Codeforces 1780E)
Tags: Math, number theory

Josuke received a huge undirected weighted complete$$$^\dagger$$$ graph $$$G$$$ as a gift from his grandfather. The graph contains $$$10^{18}$$$ vertices. The peculiarity of the gift is that the weight of the edge between the different vertices $$$u$$$ and $$$v$$$ is equal to $$$\gcd(u, v)^\ddagger$$$. Josuke decided to experiment and make a new graph $$$G'$$$. To do this, he chooses two integers $$$l \le r$$$ and deletes all vertices except such vertices $$$v$$$ that $$$l \le v \le r$$$, and also deletes all the edges except between the remaining vertices.Now Josuke is wondering how many different weights are there in $$$G'$$$. Since their count turned out to be huge, he asks for your help.$$$^\dagger$$$ A complete graph is a simple undirected graph in which every pair of distinct vertices is adjacent.$$$^\ddagger$$$ $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of the numbers $$$x$$$ and $$$y$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.The first line of each test case contains two numbers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$, $$$l \le 10^9$$$).

Output: For each test case print a single number — the number of different weights among the remaining edges.

Note:   The graph $$$G'$$$ for the first test case. The picture above shows that the graph has $$$2$$$ different weights.In the fifth test case, there is only one vertex from which no edges originate, so the answer is $$$0$$$.

Sample Inputs:
7
2 4
16 24
2 6
1 10
3 3
2562 2568
125 100090

Sample Outputs:
2
6
3
5
0
5
50045

Solution (Python):
import sys
t = int(sys.stdin.readline())
for _ in range(t):
    (l, r) = map(int, sys.stdin.readline().split())
    ans = 0
    n = l - 1
    ll = 1
    rr = 0
    while ll <= n:
        rr = n // (n // ll)
        ans += max(0, min(rr, r // (n // ll + 2)) - ll + 1)
        ll = rr + 1
    print(ans + max(0, r // 2 - n))

Solution (Python):
def solve():
    (L, R) = map(int, input().split())
    ans = max(0, R // 2 - L + 1)
    left = 1
    while left < L:
        C = (L + left - 1) // left
        right = (L + C - 2) // (C - 1) - 1
        ans += max(0, min(right, R // (C + 1)) - left + 1)
        left = right + 1
    print(ans)
t = int(input())
for test in range(t):
    solve()

Solution (Python):
import math
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()

def solve():
    (L, R) = map(int, input().split())
    ans = max(0, R // 2 - L + 1)
    left = 1
    while left < L:
        C = math.ceil(L / left)
        right = math.ceil(L / (C - 1)) - 1
        ans += max(0, min(right, R // (C + 1)) - left + 1)
        left = right + 1
    return ans
for _ in range(int(input())):
    print(solve())