algorithm - 如何计算集合{1,2,3,..,n}的互质子集的个数

Question

我正在解决 this task (problem I) .声明是:

集合有多少子集{1, 2, 3, ..., n}是互质的吗？如果一组整数中的每两个元素互质，则该整数集称为互质。如果两个整数的最大公约数等于 1，则它们互质。

输入

第一行输入包含两个整数n和 m ( 1 <= n <= 3000, 1 <= m <= 10^9 + 9 )

输出

输出 {1, 2, 3, ..., n} 的互质子集的数量模 m .

例子

输入:4 7输出:5

{1,2,3,4} 有 12 个互质子集: {} , {1} , {2} , {3} , {4} , {1,2} , {1,3} , {1,4} , {2,3} , {3,4} , {1,2,3} , {1,3,4} .

---

我觉得可以用素数来解决。 (跟踪我们是否使用了每个质数)..但我不确定。

我能得到一些提示来解决这个任务吗？

• 你可以在这里找到这个序列:http://oeis.org/A084422

Answer 1

好的，这是 cargo 。下面的 C 程序在 less 中得到 n=3000对我来说不到 5 秒。我向解决这个问题的团队致敬竞争环境中的问题。

该算法基于对待小和大的思想质数不同。如果素数的平方至多为 n，则该素数小。否则，它是大。观察每个数字小于或等于n 至多有一个大质因数。

我们制作了一个成对索引的表。每对的第一个组件指定正在使用的大素数的数量。第二个组成部分每对指定一组正在使用的小素数。值(value)在特定索引是不具有该使用模式的解决方案的数量包含 1 或一个大素数(我们稍后通过乘以2 的适当次方)。

我们在没有大质因数的情况下向下迭代数字 j。在每次迭代开始时，该表包含子集的计数j..n.内循环中有两个添加。第一个帐户用于通过 j 本身扩展子集，这不会增加使用中的大素数。第二个考虑将子集扩展 j乘以一个大素数，这确实如此。合适的大素数的数量是不大于 n/j 的大素数减去大素数已经在使用中，因为向下迭代意味着每个已经使用的大素数都不大于 n/j。

最后，我们对表格条目求和。表中统计的每个子集产生 2 ** k 个子集，其中 k 是一加上未使用的数量大素数，如 1 和每个未使用的大素数都可以包括在内，或者独立排除。

/* assumes int, long are 32, 64 bits respectively */
#include <stdio.h>
#include <stdlib.h>

enum {
  NMAX = 3000
};

static int n;
static long m;
static unsigned smallfactors[NMAX + 1];
static int prime[NMAX - 1];
static int primecount;
static int smallprimecount;
static int largeprimefactor[NMAX + 1];
static int largeprimecount[NMAX + 1];
static long **table;

static void eratosthenes(void) {
  int i;
  for (i = 2; i * i <= n; i++) {
    int j;
    if (smallfactors[i]) continue;
    for (j = i; j <= n; j += i) smallfactors[j] |= 1U << primecount;
    prime[primecount++] = i;
  }
  smallprimecount = primecount;
  for (; i <= n; i++) {
    if (!smallfactors[i]) prime[primecount++] = i;
  }
  if (0) {
    int k;
    for (k = 0; k < primecount; k++) printf("%d\n", prime[k]);
  }
}

static void makelargeprimefactor(void) {
  int i;
  for (i = smallprimecount; i < primecount; i++) {
    int p = prime[i];
    int j;
    for (j = p; j <= n; j += p) largeprimefactor[j] = p;
  }
}

static void makelargeprimecount(void) {
  int i = 1;
  int j;
  for (j = primecount; j > smallprimecount; j--) {
    for (; i <= n / prime[j - 1]; i++) {
      largeprimecount[i] = j - smallprimecount;
    }
  }
  if (0) {
    for (i = 1; i <= n; i++) printf("%d %d\n", i, largeprimecount[i]);
  }
}

static void maketable(void) {
  int i;
  int j;
  table = calloc(smallprimecount + 1, sizeof *table);
  for (i = 0; i <= smallprimecount; i++) {
    table[i] = calloc(1U << smallprimecount, sizeof *table[i]);
  }
  table[0][0U] = 1L % m;
  for (j = n; j >= 2; j--) {
    int lpc = largeprimecount[j];
    unsigned sf = smallfactors[j];
    if (largeprimefactor[j]) continue;
    for (i = 0; i < smallprimecount; i++) {
      long *cur = table[i];
      long *next = table[i + 1];
      unsigned f;
      for (f = sf; f < (1U << smallprimecount); f = (f + 1U) | sf) {
        cur[f] = (cur[f] + cur[f & ~sf]) % m;
      }
      if (lpc - i <= 0) continue;
      for (f = sf; f < (1U << smallprimecount); f = (f + 1U) | sf) {
        next[f] = (next[f] + cur[f & ~sf] * (lpc - i)) % m;
      }
    }
  }
}

static long timesexp2mod(long x, int y) {
  long z = 2L % m;
  for (; y > 0; y >>= 1) {
    if (y & 1) x = (x * z) % m;
    z = (z * z) % m;
  }
  return x;
}

static long computetotal(void) {
  long total = 0L;
  int i;
  for (i = 0; i <= smallprimecount; i++) {
    unsigned f;
    for (f = 0U; f < (1U << smallprimecount); f++) {
      total = (total + timesexp2mod(table[i][f], largeprimecount[1] - i + 1)) % m;
    }
  }
  return total;
}

int main(void) {
  scanf("%d%ld", &n, &m);
  eratosthenes();
  makelargeprimefactor();
  makelargeprimecount();
  maketable();
  if (0) {
    int i;
    for (i = 0; i < 100; i++) {
      printf("%d %ld\n", i, timesexp2mod(1L, i));
    }
  }
  printf("%ld\n", computetotal());
  return EXIT_SUCCESS;
}