如何计算集合{1,2,3，...，n}的互质的子集的数量 [英] How to calculate the number of coprime subsets of the set {1,2,3,..,n}
问题描述
我解决这个任务（问题一）。该声明是：
如何设置的许多子集 {1，2，3，...，N} 互素？一组整数称为互质，如果每两个元素为互质。如果他们的最大公约数等于1两个整数互质。
How many subsets of the set {1, 2, 3, ..., n} are coprime? A set of integers is called coprime if every two of its elements are coprime. Two integers are coprime if their greatest common divisor equals 1.
输入
输入的第一行包含两个整数 N 和 M （ 1＆LT; = N'LT = 3000，1＆LT; = M＆LT; = 10 ^ 9 + 9 ）
First line of input contains two integers n and m (1 <= n <= 3000, 1 <= m <= 10^9 + 9)
输出
输出的互质子集数{1，2，3，...，N} 模 M 。
示例
输入：4 7 输出：5
input: 4 7 output: 5
有 12互质子集{1,2,3,4} ： {} ， {1} ， {2} ， {3} ， {4} ， {1,2} ， {1,3} ， {1,4} ， {2,3} ， {3 ，4} ， {1,2,3} ， {1,3,4} 。
There are 12 coprime subsets of {1,2,3,4}: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}.
我想它可以通过使用素数来解决。 （跟踪，如果我们使用的每一个素数）..但我不知道。
I think it can be solved by using prime numbers. (keeping track of if we used each prime numbers) ..but I'm not sure.
我可以得到一些提示来解决这个任务？
Can I get some hints to solve this task?
- 您可以在这里找到这个序列： http://oeis.org/A084422
推荐答案
好了，这里的商品。接下来的C程序获取以下N = 3000 5秒对我来说。我的帽子的关闭的球队（县），解决了这一 问题在竞争环境。
Okay, here’s the goods. The C program that follows gets n=3000 in less than 5 seconds for me. My hat’s off to the team(s) that solved this problem in a competitive setting.
该算法是基于处理所述小和大的想法 素数不同。一个主要的的小的，如果它的平方是最多n。 否则，它的大的。观察到，每个号码小于或等于 n具有至多有一个大的主要因素。
The algorithm is based on the idea of treating the small and large primes differently. A prime is small if its square is at most n. Otherwise, it’s large. Observe that each number less than or equal to n has at most one large prime factor.
我们通过做对索引的表。每对中的第一组分 指定的大素数中使用的数量。的第二组分 每一对指定了一套使用小素数。在价值 尤其是指数的解决方案的数量与使用模式不 含有1个或一个大素数（我们通过乘算靠后 2相应的功率）。
We make a table indexed by pairs. The first component of each pair specifies the number of large primes in use. The second component of each pair specifies the set of small primes in use. The value at a particular index is the number of solutions with that usage pattern not containing 1 or a large prime (we count those later by multiplying by the appropriate power of 2).
我们向下遍历号码j表示使用没有大的质的因素。在 开始每次迭代，所述表包含子集的计数 的j..n。有两个添加在内部循环。第一帐户 对于用j本身，这不增加的数量延伸子集 大素数的使用。第二占用j延伸子集 次大素，这确实。合适的大素数的数目是 的大素数不大于n / J数量越多，减去的数 大素数已在使用中，由于向下迭代意味着 每一个大素已在使用不大于n / J更大。
We iterate downward over numbers j with no large prime factors. At the beginning of each iteration, the table contains the counts for subsets of j..n. There are two additions in the inner loop. The first accounts for extending subsets by j itself, which does not increase the number of large primes in use. The second accounts for extending subsets by j times a large prime, which does. The number of suitable large primes is the number of large primes not greater than n/j, minus the number of large primes already in use, since the downward iteration implies that each large prime already in use is not greater than n/j.
最后，我们总结了表条目。表中的计数每个子集 引起2 ** K个子集，其中k是一加的未使用的数 大素数，为1，每个未使用的大素可包含或 独立的除外。
At the end, we sum the table entries. Each subset counted in the table gives rise to 2 ** k subsets where k is one plus the number of unused large primes, as 1 and each unused large prime can be included or excluded independently.
/* 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;
}
这篇关于如何计算集合{1,2,3，...，n}的互质的子集的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
