c++ - 使用 K 种颜色的不同项链的数量

Question

我的任务是在 C++ 中使用 K 种颜色找出不同项链的数量。

Two necklaces are considered to be distinct if one of the necklaces cannot be obtained from the second necklace by rotating the second necklace by any angle . Find the total number of distinct necklaces modulo (10^9+7).

我觉得这个公式很好解决一个问题:

我用 C++ 实现了一个程序:

#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int M = 1e9 + 7;

int main()
{
    long long  n, k;
    cin >> n >> k;

    long long x = 0;
    for (int i = 0; i < n; ++i) {
        x += pow(k, __gcd(i,n));
    }

    cout << (int)(((double)1/n) * x) % M;
    return 0;
}

我将我的代码粘贴到带有测试用例的程序中，但我的解决方案通过了一半的测试用例。我找不到我的错误，我只看到一个测试用例。第一个测试用例是n = 5 和k = 2，答案是8。我可能在哪里犯错？

Answer 1

实际上，您的公式不正确。可以在此处找到正确的:https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_necklaces

我的实现只有 passed all the tests .