使用 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

抱歉，如果您的公式不正确，我也没办法，但这是您公式的正确实现方式

在您的代码中，循环变量 i 与公式不同。您正在移动 i=0,...,n-1，但公式显示 i=1,2,....n.

更新： 我认为您的行 x += pow(k, __gcd(i,n)); 不太正确。当 x+pow(k, __gcd(i,n)) 大于 10^9 +7 时，您应该取模，但您没有这样做。

只是为了让代码清晰，Modulo操作是分配给+的，所以你可以写成

    ( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c

但是 Modulo 对 / 没有分配性，所以你不能只写

   ( a / b ) % c = ( ( a % c ) / ( b % c ) ) % c

要计算 (x/y)%M 你必须计算

    (x * MMI(y)) % M

感谢@ivlad 指出 MMI 缺陷:)

改变

 for (int i = 0; i < n; ++i) {
    x += pow(k, __gcd(i,n));
 }
 cout << (int)(((double)1/n) * x) % M;

至（这是一个完整的答案）

  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;
 }

Answer 2

考虑数量限制。

long long 可以是 unsigned long long 甚至 long double.

double 可以是 long double。这实际上是平台相关的，但可能是原因。

顺便说一下，n被定义为long long，它真的太大了吗？？如果是，你的循环将花费很长时间，你可能会得到 "Time Limit Exceeded"。如果不是，只需声明它 int。声明它 long long 而 int 就足够了可能会导致一些错误！！

Answer 3

我发现您的程序有两处错误。第一个是即使 k 和 n 的值很小，pow 也会溢出。根据输入的大小（您不提供），pow 甚至在您取模之前就可能溢出。您应该将 pow 替换为您自己的 powModM，这样会更频繁地使用 % M。像

int powModM(int k, int n, int M) {
  int res = 1;
  for (int i = 0; i < n; ++i) {
    res = (res * k) % M;
  }
  return res;
}

尽管如果指数很大，您可能希望将其替换为使用 O(log n) 快速求幂的过程。

第二个更大的问题是除以 n。与加法、减法和乘法不同，模算术中的除法不能通过在普通算术中执行除法然后取模来完成。一方面，如果 gcd(n,10^9+7) != 1，您可能会除以 0。（但是，由于 10^9+7 是质数，所以这不太可能，我会忽略这个问题）。另一个更可能的问题是，在模运算中除以 n，您必须乘以 n 的倒数，这与 1/n.[=26= 完全不同]

这是一个 Java 例程，使用扩展欧几里德算法计算乘法逆。您可以轻松地将其改编为 C++。注意函数中的商q是整数除法计算的

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;
  }

Answer 4

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

我的实现只有 passed all the tests。

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

Number of distinct necklaces using K colors

c++

algorithm

math

combinatorics