### ZOJ Monthly, November 2010解题报告 » ZOJ3434

ZOJ3434.cpp

```#include <vector>
#include <cstdio>
#include <cassert>
#include <algorithm>

using namespace std;

const int MAXN = 22;
const int MAXM = 100100;
const int MAXL = 1 << 20;

vector<int> p[MAXL];

bool ok[MAXL];
long long dp[MAXL];

int main() {
int re;
int n, m, l, a, b;
long long ans;

for (int i = 2; i < MAXL; ++i) {
if (p[i].empty()) {
for (int j = i; j < MAXL; j += i) {
p[j].push_back(i);
}
}
}

scanf("%d", &re);
for (int ri = 1; ri <= re; ++ri) {
scanf("%d%d%d", &n, &m, &l);

fill(ok, ok + l + 1, false);
ok[0] = true;
for (int i = 0; i < n; ++i) {
scanf("%d", &a);
for (int j = a; j <= l; ++j) {
ok[j] |= ok[j - a];
}
}

fill(dp, dp + l + 1, 0);
for (int i = 0; i < m; ++i) {
scanf("%d", &b);
++dp[b];
}
for (int i = 2; i <= l; ++i) {
for (int j = 0; j < (int)p[i].size(); ++j) {
dp[i] += dp[i / p[i][j]];
}
}

ans = 0;
for (int i = 1; i <= l; ++i) {
if (ok[i]) {
// printf("%d %lld\n", i, dp[i]);
ans += dp[i];
}
}
printf("%lld\n", ans);
}

return 0;
}

// Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
// 374 	2010-11-10 00:18:09 	Accepted 	H 	C++ 	1950 	45972 	watashi@Zodiac 	Source
```