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

Question

我有一个任务，在C++中使用K个颜色查找不同项链的数量。

如果一个项链不能通过旋转第二个项链的任何角度获得第二个项链，则认为两个项链是不同的。找到模（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。 我可能犯了什么错误？

- rel1x

---

++i 并不是你想象中的那样。具体来说，for循环条件总是按照初始化器、终止条件和增量器的顺序进行评估。因此，在for循环中写入 ++i或 i++都没有关系。但由于 ++i可能会误导人们认为循环正在执行其他操作，因此始终建议使用 i++ 作为自我记录的提醒，以说明正在发生的事情。 - slebetman

@rel1x 我已经更新了答案，请查看。 - Karthik

所有当前的答案很可能都是错误的，因为在for循环之后，即使对于n和k都很小的情况下，x也很可能超过甚至是long long。取模运算是有原因的：你必须在每一步计算它。 - IVlad

@slebetman 嗯，相反的是正确的。在C++中，总是使用++i而不是i++。原因是后者有时比前者慢 - 不适用于像int这样的内置类型，但适用于自定义类型。无论如何，在这里它们的语义是相同的，所以我不明白其中一个会让人困惑... - Konrad Rudolph

你能发一下问题链接吗？ - Shubham Sharma

Answer 1

实际上，你的公式是不正确的。 正确的公式可以在此处找到：https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_necklaces 我的实现刚刚通过了所有测试。你可以查看这里。

- dened

Answer 2

抱歉，如果您的公式不正确，我无法提供帮助，但这是您公式的正确实现方式

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

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

只是为了使代码更清晰，模运算操作在+上是分配的。因此，您可以编写

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

但是模运算不满足/的分配律，因此您不能简单地写成

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

to (这是完整的答案)

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

- Karthik

---

这是错误的：在取模之后不能再除以 n，然后再次进行取模。这会得到错误的答案。 - IVlad

@IVlad，我没听懂你的意思。 - Karthik

你计算了 x 对 M 取模。然后你将该结果除以 n。这是错误的。 - IVlad

rel1x，你可以尝试这个更新的解决方案。 - Karthik

似乎@IVlad在谈论其他事情。 - Bob Napkin

Answer 3

我看到你的程序有两个问题。第一个是即使对于小的 k 和 n 值，pow 函数可能会溢出。根据输入的大小（你没有提供），pow 可能甚至在取模之前就已经溢出了。你应该用自己的 powModM 替换 pow，它更频繁地进行 % 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，则可能会被零除。（但是，由于10^9+7是质数，这是非常不可能的，我会忽略这个问题）。另一个更可能的问题是，在模算术中除以 n，必须相反地乘以 n 的逆元素，这与 1/n 完全不同。

这是一个使用扩展欧几里得算法计算乘法逆元素的 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;
  }

- Edward Doolittle

---

我不理解反向（inverse）的含义，参数 a 和 m 分别代表什么？ - rel1x

a 是你的 n，而 m 是你的 M。 - Edward Doolittle

Answer 4

考虑数字限制。

long long 可以是 unsigned long long 或者甚至是 long double。

double 可以是 long double。这实际上取决于平台，但可能是原因之一。

顺便说一下，n 被声明为 long long，它真的可以那么大吗？如果是，你的循环将需要很长时间，而且你可能会得到“超时”的错误提示。如果不是，只需将其声明为 int。在已经足够使用 int 的情况下将其声明为 long long 可能会导致一些错误！

- user586399

---

即使 n 很小，指数计算也会导致整个表达式溢出。 - IVlad