# Number of distinct necklaces using K colors

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?

• What means modulo 109+7? Jul 5 '15 at 15:11
• sorry, 10^9+7. I updated question. Jul 5 '15 at 15:14

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.

• thank you so much, I updated my code using your advices, but noting changed. I think I make a mistake again. Could you please check it ideone.com/ZvFvSO Jul 5 '15 at 14:59
• You are not doing the division by $n$ properly. As an example of what the problem is, lets suppose that we are working modulo $5$ and we want to divide the number $9$ by the number $3$. Since everything is modulo $5$, we want to calculate $4/3$ mod $5$. Now if we just take the integer part of $4/3$, which is effectively what your code is doing, then we get the answer $1$, when the answer should be $3$. What we have do do instead is find an integer $m$ such that $3m\equiv1$ mod $5$ and multiply $4$ by this value. In this case, $3\cdot2\equiv1$ mod $5$, and $4\cdot2\equiv3$ mod $5$ like we want. Jul 5 '15 at 15:35
• In your case, to divide $\verb+x+$ by $n$, we find an integer $m$ such that $mn \equiv 1$ mod $10^9+7$ and multiply $\verb+x+$ by this value. You may want to look at the extended Euclidean algorithm. Jul 5 '15 at 15:37