Square Counting (Codeforces 1646A)
Tags: Math, math

Luis has a sequence of $$$n+1$$$ integers $$$a_1, a_2, \ldots, a_{n+1}$$$. For each $$$i = 1, 2, \ldots, n+1$$$ it is guaranteed that $$$0\leq a_i < n$$$, or $$$a_i=n^2$$$. He has calculated the sum of all the elements of the sequence, and called this value $$$s$$$. Luis has lost his sequence, but he remembers the values of $$$n$$$ and $$$s$$$. Can you find the number of elements in the sequence that are equal to $$$n^2$$$?We can show that the answer is unique under the given constraints.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$). Description of the test cases follows.The only line of each test case contains two integers $$$n$$$ and $$$s$$$ ($$$1\le n< 10^6$$$, $$$0\le s \le 10^{18}$$$). It is guaranteed that the value of $$$s$$$ is a valid sum for some sequence satisfying the above constraints.

Output: For each test case, print one integer — the number of elements in the sequence which are equal to $$$n^2$$$.

Note: In the first test case, we have $$$s=0$$$ so all numbers are equal to $$$0$$$ and there isn't any number equal to $$$49$$$.In the second test case, we have $$$s=1$$$. There are two possible sequences: $$$[0, 1]$$$ or $$$[1, 0]$$$. In both cases, the number $$$1$$$ appears just once. In the third test case, we have $$$s=12$$$, which is the maximum possible value of $$$s$$$ for this case. Thus, the number $$$4$$$ appears $$$3$$$ times in the sequence.

Sample Inputs:
4
7 0
1 1
2 12
3 12

Sample Outputs:
0
1
3
1

Solution (Python):
for s in [*open(0)][1:]:
    (n, s) = map(int, s.split())
    print(s // n // n)

Solution (Python):
for input_line in [*open(0)][1:]:
    (n, s) = map(int, input_line.split())
    result = s // n // n
    print(result)

Solution (Python):
import sys
from functools import wraps, lru_cache
import functools
sys.stdin.reconfigure(line_buffering=True)
input = lambda : sys.stdin.readline().rstrip()
ii = lambda : int(input())
si = lambda : input()
mi = lambda : map(int, input().split())
mf = lambda : map(float, input().split())
msi = lambda : map(str, input().strip().split(' '))
li = lambda : list(mi())
lf = lambda : list(mf())

def YES():
    print('YES')

def Yes():
    print('Yes')

def yes():
    print('yes')

def NO():
    print('NO')

def No():
    print('No')

def no():
    print('no')

class Solution:

    def __init__(self):
        return

    def turbo(func):
        cache = {}

        @wraps(func)
        def wrapper(*args, **kwargs):
            key = str(args) + str(kwargs)
            if key not in cache:
                cache[key] = func(*args, **kwargs)
            return cache[key]
        return wrapper

    def ignore_unhashable(func):
        uncached = func.__wrapped__
        attributes = functools.WRAPPER_ASSIGNMENTS + ('cache_info', 'cache_clear')

        @functools.wraps(func, assigned=attributes)
        def wrapper(*args, **kwargs):
            try:
                return func(*args, **kwargs)
            except TypeError as error:
                if 'unhashable type' in str(error):
                    return uncached(*args, **kwargs)
                raise
        wrapper.__uncached__ = uncached
        return wrapper

    @staticmethod
    @ignore_unhashable
    @lru_cache(maxsize=128)
    @turbo
    def solve():
        for _ in range(ii()):
            (a, b) = mi()
            print(b // a ** 2)
if __name__ == '__main__':
    Solution().solve()