Partitioning the Array (Codeforces 1920C)
Tags: Math, number theory

Allen has an array $$$a_1, a_2,\ldots,a_n$$$. For every positive integer $$$k$$$ that is a divisor of $$$n$$$, Allen does the following:  He partitions the array into $$$\frac{n}{k}$$$ disjoint subarrays of length $$$k$$$. In other words, he partitions the array into the following subarrays: $$$$$$[a_1,a_2,\ldots,a_k],[a_{k+1}, a_{k+2},\ldots,a_{2k}],\ldots,[a_{n-k+1},a_{n-k+2},\ldots,a_{n}]$$$$$$  Allen earns one point if there exists some positive integer $$$m$$$ ($$$m \geq 2$$$) such that if he replaces every element in the array with its remainder when divided by $$$m$$$, then all subarrays will be identical. Help Allen find the number of points he will earn.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. 

Output: For each test case, output a single integer — the number of points Allen will earn.

Note: In the first test case, $$$k=2$$$ earns a point since Allen can pick $$$m = 2$$$ and both subarrays will be equal to $$$[1, 0]$$$. $$$k=4$$$ also earns a point, since no matter what $$$m$$$ Allen chooses, there will be only one subarray and thus all subarrays are equal.In the second test case, Allen earns $$$1$$$ point for $$$k=3$$$, where his choice for $$$m$$$ does not matter.

Sample Inputs:
8
4
1 2 1 4
3
1 2 3
5
1 1 1 1 1
6
1 3 1 1 3 1
6
6 2 6 2 2 2
6
2 6 3 6 6 6
10
1 7 5 1 4 3 1 3 1 4
1
1

Sample Outputs:
2
1
2
4
4
1
2
1

Solution (Python):
from math import gcd

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    b = [0] * (n + 1)
    for i in range(1, n + 1):
        if n % i != 0:
            continue
        if b[i] == 1:
            ans += 1
            continue
        x = 0
        for j in range(1, n - i + 1):
            x = gcd(x, abs(a[j - 1] - a[j - 1 + i]))
            if x == 1:
                break
        if x != 1:
            ans += 1
            for j in range(i, n + 1, i):
                b[j] = 1
    print(ans)
for _ in range(int(input())):
    solve()

Solution (Python):
def gcd(a, b):
    if b == None:
        return a
    if b == 0:
        return a
    elif a == 0:
        return b
    else:
        return gcd(b, a % b)
for i in range(int(input())):
    n = int(input())
    l = [int(i) for i in input().split()]
    c = 1
    for i in range(1, n):
        if n % i != 0:
            continue
        g = None
        for j in range(i):
            for k in range(j + i, n, i):
                g = gcd(abs(l[k] - l[k - i]), g)
            if g == 1:
                break
        else:
            c += 1
    print(c)

Solution (Python):
from math import *

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 1
    f = [0] * (n + 1)
    for k in range(1, n):
        if f[k] == 1:
            continue
        if n % k == 0:
            g = 0
            for i in range(k, n):
                g = gcd(g, a[i] - a[i % k])
                if g < 0:
                    g *= -1
                if g == 1:
                    break
            if g != 1:
                for kk in range(k, n, k):
                    if f[kk] == 0 and n % kk == 0:
                        ans += 1
                        f[kk] = 1
    print(ans)

def main():
    for _ in range(int(input())):
        solve()
if __name__ == '__main__':
    main()