## 题目大意

```for i = 1 to M do
for j = 1 to N do
if j % B[i] == 0 then
A[j] = A[j] * C[i]
endif
end do
end do
```

## 数据范围

1≤ N,M ≤ 10^5

1 ≤ B[i] ≤ N

1 ≤ A[i],C[i] ≤10^5

## 筛法

`j % B[i] == 0`这个关系我们可以很容易的联想到筛法，我们不必要从1到N每次去尝试是否可以被B[i]整除，而是直接在数组A的第`B[i], B[i] * 2 ... B[i] * k`项上直接乘上C[i]。

## Show me the code

```#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

typedef long long llint;

const int SIZE = 100010;
const int MOD = 1000000007;

struct node {
int vb, vc;

friend bool operator < (const node& a, const node& b) {
return a.vb < b.vb;
}
};

node nodes[SIZE];

int A[SIZE];

int n, m;

void solve()
{
llint g = 1;
int pre = -1;
for (int i = 1; i <= m + 1; i++) {
if (nodes[i].vb == pre) {
g *= nodes[i].vc;
g %= MOD;
}
if (nodes[i].vb != pre || i == m + 1) {
int b = pre;
for (int j = 1; b * j <= n && b != -1; j++) {
int pa = b * j;
A[pa] = llint(A[pa]) * g % MOD;
}
g = nodes[i].vc;
pre = nodes[i].vb;
}
}
}

int main()
{
input(n >> m);
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
for (int i = 1; i <= m; i++) {
scanf("%d", &(nodes[i].vb));
}
for (int i = 1; i <= m; i++) {
scanf("%d", &(nodes[i].vc));
}
sort(nodes + 1, nodes + m + 1);
solve();
for (int i = 1; i <= n; i++) {
printf("%d ", A[i] % MOD);
}
puts("");
return 0;
}
```

## 关键点

• 是否了解筛法，并且可以从题目的提示中联想到筛法
• 是否了解调和级数估计时间复杂度的方法
• 是否了解算法的best-case和worst-case
• 是否可以了解算法的瓶颈，并优化自己的算法

• 本图来自《算法 第四版》