Like rotate_gcd, but calculates the gcd by traversing the first cycle.

rotate_no_gcd.cpp

#include <cassert>
#include <iterator>
#include <numeric>
#include <utility>

#ifndef NDEBUG
#include <cassert>
#define EXPECT(...) assert(__VA_ARGS__)
#else
#ifdef __clang__
#define EXPECT(...) (static_cast<void>(!!(__VA_ARGS__)), __builtin_assume(!!(__VA_ARGS__)))
#elif _MSC_VER
#define EXPECT(...) (static_cast<void>(!!(__VA_ARGS__)), __assume(!!(__VA_ARGS__)))
#elif __GNUC__
#define EXPECT(...) ((__VA_ARGS__) ? void() : __builtin_unreachable())
#else
#define EXPECT(...) (static_cast<void>(!!(__VA_ARGS__)))
#endif
#endif

template<class I>
    // requires RandomAccessIterator<I>() && Permutable<I>()
constexpr I rotate_no_gcd(I first, I const mid, I const last) {
    using D = typename std::iterator_traits<I>::difference_type;
    using V = typename std::iterator_traits<I>::value_type;

    EXPECT(first <= mid);
    EXPECT(mid <= last);

    D const len = last - first;
    EXPECT(len >= 0);
    D const m = mid - first;
    EXPECT(0 <= m && m <= len);

    if (0 == m) {
        return first;
    }

    // Traverse one cycle and count its length
    D dst = 0;
    D cycle_length = 0;
    V tmp = std::move(first[dst]);
    for(;;) {
        ++cycle_length;

        D src = dst + m;
        if (src >= len) {
            src -= len;
        }

        if (src == 0) {
            break;
        }

        first[dst] = std::move(first[src]);
        dst = src;
    }

    // calculate gcd(m, len)
    EXPECT(len % cycle_length == 0);
    EXPECT(len / cycle_length == std::gcd(m, len));
    D const n_cycles = len / cycle_length;

    // traverse the remaining (n_cycles - 1) cycles
    D first_in_cycle = 0;
    for (;;) {
        first[dst] = std::move(tmp);
        dst = ++first_in_cycle;
        if (dst == n_cycles) {
            break;
        }

        tmp = std::move(first[first_in_cycle]);
        for (;;) {
            D src = dst + m;
            if (src >= len) {
                src -= len;
            }

            if (src == first_in_cycle) {
                break;
            }

            first[dst] = std::move(first[src]);
            dst = src;
        }
    }

    return first + (len - m);
}

#include <algorithm>
#include <numeric>

int main() {
    static constexpr int N = 2*2*3*5*7*7;
    int some_ints[N];
    int control[N];

    std::iota(std::begin(some_ints), std::end(some_ints), 0);
    for (auto i = 0; i < N; ++i) {
        std::copy_n(some_ints, N, control);
        auto x = rotate_no_gcd(std::begin(some_ints), std::begin(some_ints) + 2, std::end(some_ints));
        auto y = std::rotate(std::begin(control), std::begin(control) + 2, std::end(control));
        assert(x - std::begin(some_ints) == y - std::begin(control));
        assert(std::equal(std::begin(some_ints), std::end(some_ints), std::begin(control), std::end(control)));
    }
}