题目链接：
CF402D
题目分析：
首先考虑一下怎么求每个数的分数。把每个数分解到最后会发现它的坏质因子对它分数的贡献是\(-1\)，好质因子对它分数的贡献是\(1\)，那么最后的分数就是好质因数-坏质因数
然后想一想怎么操作。我们的最优答案是把所有能除掉的负数分数的\(gcd\)全部除掉，一个很显然的贪心是从后往前操作，因为前面操作了之后后面的\(gcd\)就恒为\(1\)，操作不下去了
另一个\(point\)是操作是显然正确的，因为后面的操作会除掉前面操作原本的\(gcd\)的一部分，而剩下的一部分应该被除掉的会在之后的贪心中被除去
举个例子 假设区间\([1, 5]\)需要被除掉的\(gcd\)是\(12\)，区间\([1, 9]\)需要被除掉的\(gcd\)是\(4\)，那么在\(9\)号位上除去\(4\)后再在\(5\)号位上除去\(3\)即可
处理一下前缀\(gcd\)，从后向前贪心，并记录当前已经除去了多少，每次进行操作之前要先除去这个量。（另：素数只需筛到\(sqrt(1e9)\)即可，后面的可以暴力判断），对于每一位，质因数分解一下当前位置上的前缀\(gcd\)并计算它的分数，如果\(<0\)就除掉它
用\(bitset\)记录坏质数
代码：
#include<bits/stdc++.h>
#define N (100000 + 5)
using namespace std;
int n, m, prime[N], tot, ans, g[N];
bool vis[N];
bitset <1000000005> S;inline int read() {
int cnt = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}
return cnt * f;
}
int a[N], b[N];
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
void init() {
for (register int i = 2; i <= N - 5; ++i) {
if (!vis[i]) vis[i] = 1, prime[++tot] = i;
for (register int j = 1; j <= tot && prime[j] * i <= N - 5; ++j) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int divide(int x) {
int ans = 0;
for (register int i = 1; i <= tot && prime[i] * prime[i] <= x; ++i) {
while (x % prime[i] == 0) ans += S[prime[i]] ? -1 : 1, x /= prime[i];
}
if (x > 1) ans += S[x] ? -1 : 1;
return ans;
}
int main() {
n = read(), m = read();
for (register int i = 1; i <= n; ++i) a[i] = read();
for (register int i = 1; i <= m; ++i) S[read()] = 1;
init();
for (register int i = 1; i <= n; ++i) ans += divide(a[i]);
for (register int i = 1; i <= n; ++i) g[i] = gcd(g[i - 1], a[i]);
int div = 1;
for (register int i = n; i >= 1; --i) {
g[i] /= div;
int x = divide(g[i]);
if (x < 0) ans += i * (-x), div *= g[i];
}
printf("%d\n", ans);
return 0;
}
