Row Major (Codeforces 1844D)
Tags: Math, number theory

The row-major order of an $$$r \times c$$$ grid of characters $$$A$$$ is the string obtained by concatenating all the rows, i.e. $$$$$$ A_{11}A_{12} \dots A_{1c}A_{21}A_{22} \dots A_{2c} \dots A_{r1}A_{r2} \dots A_{rc}. $$$$$$A grid of characters $$$A$$$ is bad if there are some two adjacent cells (cells sharing an edge) with the same character.You are given a positive integer $$$n$$$. Consider all strings $$$s$$$ consisting of only lowercase Latin letters such that they are not the row-major order of any bad grid. Find any string with the minimum number of distinct characters among all such strings of length $$$n$$$.It can be proven that at least one such string exists under the constraints of the problem.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output a string with the minimum number of distinct characters among all suitable strings of length $$$n$$$.If there are multiple solutions, print any of them.

Note: In the first test case, there are $$$3$$$ ways $$$s$$$ can be the row-major order of a grid, and they are all not bad: tththathatat It can be proven that $$$3$$$ distinct characters is the minimum possible.In the second test case, there are $$$2$$$ ways $$$s$$$ can be the row-major order of a grid, and they are both not bad: iiss It can be proven that $$$2$$$ distinct characters is the minimum possible.In the third test case, there is only $$$1$$$ way $$$s$$$ can be the row-major order of a grid, and it is not bad.In the fourth test case, there are $$$4$$$ ways $$$s$$$ can be the row-major order of a grid, and they are all not bad: ttotomtomatoomaatomtoato It can be proven that $$$4$$$ distinct characters is the minimum possible. Note that, for example, the string "orange" is not an acceptable output because it has $$$6 > 4$$$ distinct characters, and the string "banana" is not an acceptable output because it is the row-major order of the following bad grid: banana

Sample Inputs:
4
4
2
1
6

Sample Outputs:
that
is
a
tomato

Solution (Python):
import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
    n = inp()
    ans = 0
    for i in range(2, n):
        if n % i != 0:
            ans = i
            break
    if ans == 0:
        ans = n
    s = 'abcdefghijklmnopqrstuvwxyz'
    k = s[:ans]
    m = n // ans
    ans1 = k * m
    h = n % ans
    ans1 += s[:h]
    print(ans1)

def main():
    testcases = 1
    testcases = inp()
    for each_testcase in range(testcases):
        solve()

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

def inps():
    return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Solution (Python):
inf = pow(2, 61) - 1
t = int(input())
alpha = 'qwertyuiopasdfghjklzxcvbnm'
for i in range(t):
    n = int(input())
    mex = 0
    for i in range(1, n + 5):
        if n % i != 0:
            mex = i
            break
    print((alpha[:mex] * ((n + mex - 1) // mex))[:n])

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    char = 'abcdefghijklmnopqrstuvwxyz'
    i = 1
    while n % i == 0:
        i += 1
    q = n // i
    r = n % i
    ans = char[:i] * q + char[:r]
    print(ans)