算法：求遍历数组所有元素所需循环次数（非暴力法）

Alright, let's cut to the chase—this problem doesn't require any brute-force array traversal at all. It's a classic number theory problem solved using the Greatest Common Divisor (GCD) of n and k.

Core Insight #

When you jump k elements each time in an array of size n, you'll end up splitting the array into several independent cycles. Each cycle is a subset of elements you'll loop through before returning to your starting point. The number of these distinct cycles you need to complete to cover every element is exactly equal to the GCD of n and k.

Let's confirm with concrete examples to make this stick:

• Example 1: n=6, k=2. GCD(6,2)=2. You have two cycles: 0→2→4→0 and 1→3→5→1. So you need 2 cycles to traverse all elements.
• Example 2: n=5, k=2. GCD(5,2)=1. There's only one cycle: 0→2→4→1→3→0. So you just need 1 cycle.
• Example 3: n=12, k=4. GCD(12,4)=4. The cycles are 0→4→8→0, 1→5→9→1, 2→6→10→2, 3→7→11→3—4 cycles total.

Why This Works #

Let’s break down the math quickly:
Let d = gcd(n, k). We can rewrite n as d * n' and k as d * k', where gcd(n', k') = 1 (since we've factored out the greatest common divisor).

• Each cycle will have exactly n' elements (because since k' and n' are coprime, adding k' repeatedly modulo n' will cover every number from 0 to n'-1 before looping back).
• Since there are d distinct starting points (0, 1, ..., d-1), each leading to its own cycle, the total number of cycles is d—which is exactly gcd(n, k).

Non-Brute-Force Implementation #

To compute this, you just need a fast way to calculate the GCD of n and k. The standard method is the Euclidean Algorithm, which runs in O(log(min(n,k))) time—way faster than any brute-force approach.

Here's a simple Python snippet that returns the number of cycles:

def count_cycles(n, k):
    # Euclidean algorithm to find GCD
    a, b = n, k
    while b != 0:
        a, b = b, a % b
    return a

Test it with our examples:

• count_cycles(6,2) returns 2 ✔️
• count_cycles(5,2) returns 1 ✔️
• count_cycles(12,4) returns 4 ✔️

Quick Clarification #

If you actually meant the number of steps needed to complete one full cycle (instead of the number of distinct cycles), that would be n / gcd(n,k)—but based on your question description, the count of independent cycles needed to traverse all elements is what you're after, which is gcd(n,k).

内容的提问来源于stack exchange，提问作者tiny_giant