Sum of Sortable Block Lengths

You are given an integer array nums of length

n

. An integer

k

is defined as 'sortable' if

k

is a divisor of

n

and the array nums can be transformed into a non-decreasingly sorted array by performing the following operations: Partition the array into

n/k

consecutive subarrays, each of length

k

. Independently rotate each subarray cyclically (left or right) any number of times. Your task is to find and return the sum of all such sortable integers

k

. Constraints:

1 \le n \le 10^5

-10^9 \le nums[i] \le 10^9

Python3Prefix SumHashingDivisor Iteration

Read