Number of individual necklaces using K colors
I have a task to find the number of different necklaces using K colors in C ++.
Two necklaces are considered excellent if one of the necklaces cannot be obtained from the second necklace by rotating the second necklace at any angle. Find the total number of individual necklaces modulo (10 ^ 9 + 7).
I think this formula is good for solving the problem:
And I have implemented the 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 = 0; i < n; ++i) {
x += pow(k, __gcd(i,n));
}
cout << (int)(((double)1/n) * x) % M;
return 0;
}
I am pasting my code into a program with test cases, but my solution passed half of the test cases. I cannot find my error and I only see one test case. The first test case is n = 5
and k = 2
, and the answer is 8
. Where could I have made a mistake?
source to share
Actually, your formula is wrong. The correct one can be found here: https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_necklaces
My implementation from it just passed all the tests .
source to share
Sorry, can't help if your formula is not correct, but this is the correct implementation for your formula
In your code, the loop variable is i
different from the formula. You move i=0,...,n-1
, but the formula speaks i=1,2,....n
.
UPDATE: I think your line is x += pow(k, __gcd(i,n));
not entirely correct. When there x+pow(k, __gcd(i,n))
is more than 10 ^ 9 +7, you should accept modulo, but you don't.
To keep the code clean, operations Modulo
are distributive over +
, so you can write
( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c
But Modulo
it is not distributive over /
, so you cannot just write
( a / b ) % c = ( ( a % c ) / ( b % c ) ) % c
To calculate (x/y)%M
you need to calculate
(x * MMI(y)) % M
Thank you @ivlad for pointing out the flaw in MMI :)
change
for (int i = 0; i < n; ++i) {
x += pow(k, __gcd(i,n));
}
cout << (int)(((double)1/n) * x) % M;
to (This is the complete answer)
long long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
long long power(long a, long b, long MOD) {
long long x = 1, y = a;
while(b > 0) {
if(b%2 == 1) {
x=(x*y);
if(x>MOD) x%=MOD;
}
y = (y*y);
if(y>MOD) y%=MOD;
b /= 2;
}
return x;
}
long long modInverse(long n, long m) {
return power(n, m - 2, m);
}
int main()
{
long n, k;
cin >> n >> k;
for (long i = 1; i <=n; i++) {
long long power = pow(k, gcd(i,n));
x = ((x % M) + (power % M)) %M;
}
long long mmi = modInverse(n,M);
mmi = (x*mmi)%M;
cout << mmi;
return 0;
}
source to share
I see two things wrong with your program. First, it pow
will overflow even at small values of k
and n
. Depending on the size of the inputs (which you don't give) pow
may overflow even before you accept the module. You must replace it pow
with your own powModM
, which takes % M
more often. Something like
int powModM(int k, int n, int M) {
int res = 1;
for (int i = 0; i < n; ++i) {
res = (res * k) % M;
}
return res;
}
although if the exponents are large, you can replace them with a procedure using O(log n)
fast exposure.
The second, big problem is what you divide by n
. Unlike addition, subtraction, and multiplication, division by modular arithmetic cannot be achieved by performing division in normal arithmetic and then modulo. First, if gcd(n,10^9+7) != 1
, you can divide by 0. (However, since 10 ^ 9 + 7 is simple, this is unlikely and I would ignore the problem). Another, more likely problem is that to divide by n
in modular arithmetic, you must multiply by the inverse n
, which is completely different from 1/n
.
Here's a Java routine to compute the multiplicative inverse using the extended Euclidean algorithm. You can easily adapt it to C ++. Note that the factor q
in the function is calculated using integer division.
public static long inverse(long a, long m) { // mult. inverse of a mod m
long r = m;
long nr = a;
long t = 0;
long nt = 1;
long tmp;
while (nr != 0) {
long q = r/nr;
tmp = nt; nt = t - q*nt; t = tmp;
tmp = nr; nr = r - q*nr; r = tmp;
}
if (r > 1) return -1; // no inverse
if (t < 0) t += m;
return t;
}
source to share
Think about number limits.
long long
maybe unsigned long long
or even long double
.
double
maybe long double
. This is actually platform dependent, but may be the reason.
By the way, n
shares how long long
, could it be too big? If so, your cycle will take a very long time and you will probably get "Time Limit Exceeded". If not, just declare it int
. Announcement long long
while int
enough may cause some errors!