Number of distinct necklaces using K colors

Question

I have a task to find the number of distinct necklaces using K colors.

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.

I think this formula is good to solve a problem:

And I implemented a program using 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 = 1; i <= n; ++i) {
        x += pow(k, __gcd(i,n));
    }

    cout << x/n % M;
    return 0;
}

I paste my code to program with test cases but my solution passed half of test cases. I can't find my mistake and I see only one test case. First test case is n = 5 and k = 2, and answer is 8. Where I could make a mistake? I'm not about code, maybe I wrong with this formula? Maybe I need to use another formula?

Answer 1

There are a few problems with your code. Firstly, $\verb+x+$ is going to get very large very quickly, and you will get an integer overflow even using $\verb+long long+$ for the type for $\verb+x+$. For example, when $n=64$ and $k = 2$, one of the terms in your sum is $2^{64}$, which is already larger than the value which can be stored in a $\verb+long long+$.

What you will want to do instead (since it seems that you have to output your answer modulo $10^9+7$) is to calculate $k^{\gcd(i,n)}$ modulo $10^9+7$ before adding it to $x$, and then also mod the result with $10^9+7$ so that your value of $\verb+x+$ is always less than $10^9 + 7$.

You then get another problem though. When you want to divide by $n$ later, you can't simply do the division as $\verb+x/n+$. Since we now only have the value of $x$ modulo $10^9+7$, we also have to do the division modulo $10^9+7$. To do this, you will have to calculate the inverse of $n$ modulo $10^9+7$ and multiply $\verb+x+$ by this number.