Joyboard (Codeforces 1877C)
Tags: Math, number theory

Chaneka, a gamer kid, invented a new gaming controller called joyboard. Interestingly, the joyboard she invented can only be used to play one game.The joyboard has a screen containing $$$n+1$$$ slots numbered from $$$1$$$ to $$$n+1$$$ from left to right. The $$$n+1$$$ slots are going to be filled with an array of non-negative integers $$$[a_1,a_2,a_3,\ldots,a_{n+1}]$$$. Chaneka, as the player, must assign $$$a_{n+1}$$$ with an integer between $$$0$$$ and $$$m$$$ inclusive. Then, for each $$$i$$$ from $$$n$$$ to $$$1$$$, the value of $$$a_i$$$ will be equal to the remainder of dividing $$$a_{i+1}$$$ (the adjacent value to the right) by $$$i$$$. In other words, $$$a_i = a_{i + 1} \bmod i$$$.Chaneka wants it such that after every slot is assigned with an integer, there are exactly $$$k$$$ distinct values in the entire screen (among all $$$n+1$$$ slots). How many valid ways are there for assigning a non-negative integer into slot $$$n+1$$$?

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2\cdot10^4$$$) — the number of test cases. The following lines contain the description of each test case.The only line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 10^9$$$; $$$0 \leq m \leq 10^9$$$; $$$1 \leq k \leq n+1$$$) — there are $$$n+1$$$ slots, the integer assigned in slot $$$n+1$$$ must not be bigger than $$$m$$$, and there should be exactly $$$k$$$ distinct values.

Output: For each test case, output a line containing an integer representing the number of valid ways for assigning a non-negative integer into slot $$$n+1$$$.

Note: In the first test case, one of the $$$2$$$ possible ways for Chaneka is to choose $$$a_{n+1}=6$$$. If she does that, then:   $$$a_4=a_5\bmod 4=6\bmod 4=2$$$  $$$a_3=a_4\bmod 3=2\bmod 3=2$$$  $$$a_2=a_3\bmod 2=2\bmod 2=0$$$  $$$a_1=a_2\bmod 1=0\bmod 1=0$$$  $$$a = [0, 0, 2, 2, 6]$$$  There are $$$3$$$ distinct values. In the second test case, the $$$1$$$ possible way for Chaneka is to choose $$$a_{n+1}=0$$$. If she does that, then $$$a = [0, 0, 0]$$$. There is only $$$1$$$ distinct value.In the third test case, there is no possible way for assigning a non-negative integer into slot $$$n+1$$$.

Sample Inputs:
4
4 6 3
2 0 1
265 265 265
3 10 2

Sample Outputs:
2
1
0
5

Solution (Python):
import sys
import heapq
import math
input = sys.stdin.readline
from collections import Counter, deque, defaultdict

def sieve_of_eratosthenes(n):
    sieve = [True] * (n + 1)
    (sieve[0], sieve[1]) = (False, False)
    primes = []
    for current in range(2, int(n ** 0.5) + 1):
        if sieve[current]:
            primes.append(current)
            for multiple in range(current * current, n + 1, current):
                sieve[multiple] = False
    for current in range(int(n ** 0.5) + 1, n + 1):
        if sieve[current]:
            primes.append(current)
    return primes

def inp():
    return int(input())

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

def insr():
    s = input()
    return list(s[:len(s) - 1])

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

def count_divisible_by(num, limit):
    return limit // num

def sum_range(a, b):
    return b * (b + 1) // 2 - a * (a - 1) // 2

def Yes():
    print('Yes')

def No():
    print('No')

def solve():
    (n, m, k) = invr()
    if k > 3:
        print(0)
    elif k == 1:
        print(1)
    elif k == 2:
        print(min(n, m) + max(m // n - 1, 0))
    else:
        print(max(0, m - n - max(m // n - 1, 0)))

def main():
    for _ in range(inp()):
        solve()
main()

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()

def solve():
    (n, m, k) = readInts()
    if k == 1:
        return 1
    elif k == 2:
        return min(n - 1, m) + m // n
    elif k == 3:
        return 0 if m < n else m - n - m // n + 1
    else:
        return 0
for _ in range(int(input())):
    print(solve())

Solution (Python):
tests = int(input())
output = []
for x in range(tests):
    (n, m, k) = map(int, input().split())
    if k > 3:
        output.append(0)
    if k == 3:
        output.append(max(0, m - n + 1 - m // n))
    if k == 2:
        output.append(m // n + min(m, n - 1))
    if k == 1:
        output.append(1)
for o in output:
    print(o)