2010-1064

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：
先给出n个ai，通过背包得到一个元素的值都<=L的集合S
然后对于每个bi，在S集中得到它的所有倍数x
对于每个x，每次可以除掉其一个质因子，把其变为1的不同的方案数加到答案中
问最终答案为多少

解法：
首先预处理出每个数将其变为1的不同方案数有多少
假设x=p1^r1^ * p2^r2^ * ... * pn^rn^ (p1 < p2 < ... < pn)
则way[x] = way[x / (p1^r1^)] * C[r1 + r2 + ... + rn][r1]
因此可以通过dp计算上述公式

然后对于每个case，先用n个ai做一次背包
注意相同的bi需要重复计算
对于bi，直接枚举x = bi, 2 * bi, 3 * bi, ... 找出所有在S集中出现的x
然后res += way[x]即可

代码：
{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 20 + 1;
const int MAXM = 100000 + 1;
const int MAXL = 1000000 + 1;

int n, m, L, a[MAXN], b[MAXM], C[MAXN][MAXN];
bool S[MAXL];

const int MAXPRIME = 1000000 + 1;

int plist[MAXPRIME], pcount, minfactor[MAXPRIME], minfactorn[MAXPRIME], factorn[MAXPRIME], pfactorn[MAXPRIME], way[MAXPRIME], reduce[MAXPRIME];
bool mark[MAXPRIME];

inline void initPrime() {
    mark[0] = mark[1] = true;
    factorn[1] = way[1] = reduce[1] = 1;
    for (int i = 2; i < MAXPRIME; i++) {
        if (mark[i]) continue;
        for (int j = i; j < MAXPRIME; j += i) {
            if (!minfactor[j]) {
                minfactor[j] = i;
            }
        }
    }
    for (int i = 2; i < MAXPRIME; i++) {
        int j = i / minfactor[i];
        pfactorn[i] = pfactorn[j] + 1;
        if (minfactor[j] == minfactor[i]) {
            reduce[i] = reduce[j];
            minfactorn[i] = minfactorn[j] + 1;
            factorn[i] = factorn[j] / minfactorn[i] * (minfactorn[i] + 1);
        } else {
            reduce[i] = j;
            minfactorn[i] = 1;
            factorn[i] = factorn[j] << 1;
        }
        way[i] = way[reduce[i]] * C[pfactorn[i]][minfactorn[i]];
    }
}

int main() {
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    initPrime();
    int task;
    scanf("%d", &task);
    for (int oo = 0; oo < task; oo++) {
        scanf("%d%d%d", &n, &m, &L);
        memset(S, 0, sizeof(bool) * (L + 1));
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            S[a[i]] = true;
        }
        for (int i = 0; i <= L; i++) {
            if (!S[i]) continue;
            for (int j = 0; j < n; j++) {
                int l = i + a[j];
                if (l <= L) S[l] = true;
            }
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &b[i]);
        }
        sort(b, b + m);
        long long sum = 0, pre = 0;
        for (int o = 0; o < m; o++) {
            if (!o || b[o] != b[o - 1]) {
                int oo = b[o];
                long long tmpsum = 0;
                for (int i = oo, j = 1; i <= L; i += oo, j++) {
                    if (S[i]) {
                        tmpsum += way[j];
                    }
                }
                pre = tmpsum;
            }
            sum += pre;
        }
        printf("%lld\n", sum);
    }
    return 0;
}
}}}

题意：

先给出n个ai，通过背包得到一个元素的值都<=L的集合S

然后对于每个bi，在S集中得到它的所有倍数x

对于每个x，每次可以除掉其一个质因子，把其变为1的不同的方案数加到答案中

问最终答案为多少

解法：

首先预处理出每个数将其变为1的不同方案数有多少

假设x=p1^r1 * p2^r2 * ... * pn^rn (p1 < p2 < ... < pn)

则way[x] = way[x / (p1^r1)] * C[r1 + r2 + ... + rn][r1]

因此可以通过dp计算上述公式

然后对于每个case，先用n个ai做一次背包

注意相同的bi需要重复计算

对于bi，直接枚举x = bi, 2 * bi, 3 * bi, ... 找出所有在S集中出现的x

然后res += way[x]即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 20 + 1;
const int MAXM = 100000 + 1;
const int MAXL = 1000000 + 1;
int n, m, L, a[MAXN], b[MAXM], C[MAXN][MAXN];
bool S[MAXL];
const int MAXPRIME = 1000000 + 1;
int plist[MAXPRIME], pcount, minfactor[MAXPRIME], minfactorn[MAXPRIME], factorn[MAXPRIME], pfactorn[MAXPRIME], way[MAXPRIME], reduce[MAXPRIME];
bool mark[MAXPRIME];
inline void initPrime() {
    mark[0] = mark[1] = true;
    factorn[1] = way[1] = reduce[1] = 1;
    for (int i = 2; i < MAXPRIME; i++) {
        if (mark[i]) continue;
        for (int j = i; j < MAXPRIME; j += i) {
            if (!minfactor[j]) {
                minfactor[j] = i;
            }
        }
    }
    for (int i = 2; i < MAXPRIME; i++) {
        int j = i / minfactor[i];
        pfactorn[i] = pfactorn[j] + 1;
        if (minfactor[j] == minfactor[i]) {
            reduce[i] = reduce[j];
            minfactorn[i] = minfactorn[j] + 1;
            factorn[i] = factorn[j] / minfactorn[i] * (minfactorn[i] + 1);
        } else {
            reduce[i] = j;
            minfactorn[i] = 1;
            factorn[i] = factorn[j] << 1;
        }
        way[i] = way[reduce[i]] * C[pfactorn[i]][minfactorn[i]];
    }
}
int main() {
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    initPrime();
    int task;
    scanf("%d", &task);
    for (int oo = 0; oo < task; oo++) {
        scanf("%d%d%d", &n, &m, &L);
        memset(S, 0, sizeof(bool) * (L + 1));
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            S[a[i]] = true;
        }
        for (int i = 0; i <= L; i++) {
            if (!S[i]) continue;
            for (int j = 0; j < n; j++) {
                int l = i + a[j];
                if (l <= L) S[l] = true;
            }
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &b[i]);
        }
        sort(b, b + m);
        long long sum = 0, pre = 0;
        for (int o = 0; o < m; o++) {
            if (!o || b[o] != b[o - 1]) {
                int oo = b[o];
                long long tmpsum = 0;
                for (int i = oo, j = 1; i <= L; i += oo, j++) {
                    if (S[i]) {
                        tmpsum += way[j];
                    }
                }
                pre = tmpsum;
            }
            sum += pre;
        }
        printf("%lld\n", sum);
    }
    return 0;
}