1
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • $\begingroup$ What means modulo 109+7? $\endgroup$ – Masacroso Jul 5 '15 at 15:11
  • $\begingroup$ sorry, 10^9+7. I updated question. $\endgroup$ – rel1x Jul 5 '15 at 15:14
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – rel1x Jul 5 '15 at 14:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Dylan Jul 5 '15 at 15:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Dylan Jul 5 '15 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.