Physical Education Lesson (Codeforces 1928C)
Tags: Math, number theory

In a well-known school, a physical education lesson took place. As usual, everyone was lined up and asked to settle in "the first–$$$k$$$-th" position.As is known, settling in "the first–$$$k$$$-th" position occurs as follows: the first $$$k$$$ people have numbers $$$1, 2, 3, \ldots, k$$$, the next $$$k - 2$$$ people have numbers $$$k - 1, k - 2, \ldots, 2$$$, the next $$$k$$$ people have numbers $$$1, 2, 3, \ldots, k$$$, and so on. Thus, the settling repeats every $$$2k - 2$$$ positions. Examples of settling are given in the "Note" section.The boy Vasya constantly forgets everything. For example, he forgot the number $$$k$$$ described above. But he remembers the position he occupied in the line, as well as the number he received during the settling. Help Vasya understand how many natural numbers $$$k$$$ fit under the given constraints.Note that the settling exists if and only if $$$k > 1$$$. In particular, this means that the settling does not exist for $$$k = 1$$$.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. This is followed by the description of the test cases.The only line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le x < n \le 10^9$$$) — Vasya's position in the line and the number Vasya received during the settling.

Output: For each test case, output a single integer — the number of different $$$k$$$ that fit under the given constraints.It can be proven that under the given constraints, the answer is finite.

Note: In the first test case, $$$k$$$ equals $$$2, 3, 5, 6$$$ are suitable.An example of settling for these $$$k$$$:  $$$k$$$ / №$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$9$$$$$$10$$$$$$2$$$$$$1$$$$$$2$$$$$$1$$$$$$2$$$$$$1$$$$$$2$$$$$$1$$$$$$2$$$$$$1$$$$$$2$$$$$$3$$$$$$1$$$$$$2$$$$$$3$$$$$$2$$$$$$1$$$$$$2$$$$$$3$$$$$$2$$$$$$1$$$$$$2$$$$$$5$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$4$$$$$$3$$$$$$2$$$$$$1$$$$$$2$$$$$$6$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$5$$$$$$4$$$$$$3$$$$$$2$$$  In the second test case, $$$k = 2$$$ is suitable.

Sample Inputs:
5
10 2
3 1
76 4
100 99
1000000000 500000000

Sample Outputs:
4
1
9
0
1

Solution (Python):
def divisors(n):
    factors = {}
    nn = n
    i = 2
    while i * i <= nn:
        while nn % i == 0:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 1
    primes = list(factors.keys())

    def generate(k):
        if k == len(primes):
            yield 1
        else:
            rest = generate(k + 1)
            prime = primes[k]
            for factor in rest:
                prime_to_i = 1
                for _ in range(factors[prime] + 1):
                    yield (factor * prime_to_i)
                    prime_to_i *= prime
    for factor in generate(0):
        yield factor
for _ in range(int(input())):
    (n, x) = map(int, input().split())
    ans = 1
    h = n - x
    ans = set((k for k in divisors(h) if not k % 2 and k / 2 + 1 >= x))
    ans2 = set()
    if x != 1:
        h = n + x - 2
        ans2 = set((k for k in divisors(h) if not k % 2 and k / 2 + 1 >= x))
    ans = ans.union(ans2)
    print(len(ans))

Solution (Python):
from math import *
from collections import *

def divisors(n):
    l = [1, n]
    k = int(sqrt(n)) + 1
    for i in range(2, k):
        if n % i == 0:
            l.append(i)
            if i != n // i:
                l.append(n // i)
    l.sort()
    return l

def solve():
    (n, x) = map(int, input().split())
    a = n - x
    b = n + x - 2
    l1 = []
    l2 = []
    if a % 2 == 0:
        l1 = divisors(a // 2)
        l1 = list(map(lambda y: a // 2 // y + 1, l1))
        l1 = list(filter(lambda z: z >= x, l1))
    if b % 2 == 0:
        l2 = divisors(b // 2)
        l2 = list(map(lambda y: b // 2 // y + 1, l2))
        l2 = list(filter(lambda z: z >= x, l2))
    s = set(l1 + l2)
    print(len(s))
for _ in range(int(input())):
    solve()

Solution (Python):
from math import *

def div(n):
    div = set()
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            div.add(i)
            div.add(n // i)
    return list(div)
for i in range(int(input())):
    (n, x) = map(int, input().split())
    ans = 0
    L = []
    B = []
    if (n - x) % 2 == 0:
        L = div((n - x) // 2)
    if (n + x - 2) % 2 == 0:
        B = div((n + x - 2) // 2)
    j = 0
    S = list(set(L + B))
    S.sort()
    while j < len(S):
        if S[j] + 1 >= x:
            break
        j += 1
    print(len(S) - j)