$O(NlogN)$ 桶数组

问题直接模拟的挑战：

• 最直接的方法是对于每个操作 k ，遍历所有 k 的倍数下标，进行修改。

• 但是， q 和 n 最大为 300000 ，最坏情况下（ k=1 ）每次操作需要修改 n 个元素，总操作次数可能达到 300000 × 300000 ，这显然会超时。

关键观察：

注意 $F(a_i) = a_i × 33 mod 415$ ，这意味着每个数经过多次操作后，结果只与操作次数有关。

• 对于同一个操作 k 多次出现，可以合并处理：如果操作 k 出现了 c 次，那么相当于一次性应用F函数 c 次。

数学优化：

• F应用 c 次等价于乘以 33 的 c 次方模 415 ：$F^c(x) = x × (33^c mod 415) mod 415$

• 因此，我们可以先统计每个操作k出现的次数，然后对于每个 k ，计算 33 的 c 次方模 415 ，然后一次性应用到所有 k 的倍数上。

算法选择：

• 使用快速幂计算 33 的 c 次方模 415 。

• 使用数组 num 记录每个操作 k 出现的次数。

• 遍历每个 k ，如果 k 出现过（ num[k] > 0 ），则计算 $pow33 = 33^num[k] mod 415$ ，然后遍历所有 k 的倍数 j， 将 a[j] 修改为 $a[j] * pow33 mod 415$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
long long a[N];
long long num[N], mod = 415;

// 快速幂计算 a^b mod p
int fast(int a, int b, int p) {
    int res = 1;
    a = a % p;
    while (b) {
        if (b & 1) {
            res = 1LL * res * a % p;
        }
        a = 1LL * a * a % p;
        b = b / 2;
    }
    return res;
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 统计每个操作k出现的次数
    for (int i = 1; i <= q; i++) {
        int x;
        cin >> x;
        num[x]++;
    }
    
    // 处理每个出现过的k
    for (int i = 1; i <= n; i++) {
        if (num[i]) {
            long long pow33 = fast(33, num[i], mod);
            for (int j = i; j <= n; j += i) {
                a[j] = a[j] * pow33 % mod;
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}