题意：
给定n个数a[i]，然后有m个数k i 1 ≤ i ≤ m k_i \ 1 \leq i \leq mk i1≤i≤m，对于每一个k，将这n个数中未k的倍数的数字加1，一次轮询m个数，问最操作次数
以样例为例：
3 5
10
11
12
2
11
4
13
2
10 11 12
->2 倍数有10、12则变为：操作2次
11 11 13
->11 倍数有11、11则变为：操作2次
12 12 13
->4 倍数有12、12则变为：操作2次
13 13 13
->13 倍数有 13、13、13则变为：操作3次
14 14 14
->2 倍数有 14、14、14则变为：操作3次
15 15 15
总共需要操作12次
思路：
原始大小最大为3e5，如果对于m个数中的每一个，都是3e5乃至+1之后的数的因子，都要使得其增加，最大可以到6e5
所以可以筛选1-6e5每个数因子，并且保存，vector facter[x]存储x的因子有哪些
而对于m个数，如果他们的倍数是a[i]，那么就需要给a[i]进行一次操作，对答案产生一次贡献
所以第一次，我们可以统计a[i]中每个数出现的次数，并记录对应的a[i]是谁的倍数（已经得到了a[i]的因子，存放在facter[a[i]]中，a[i]的因子为x，那么x的倍数就是a[i]，所以说可以利用已经预处理出来的facter[a[i]]得到），facter[a[i]][j] 记录为每个因子，则倍数set bei[facter[a[i]][j]] = a[i]是一定可以确定的，所以说可以直接在处理过程中找到bei[k[i]]，对于每一个k的倍数x，贡献加上他们的个数cnt[x]，这里的cnt[]需要预处理，并且还要根据+1变化进行再次的统计：+1变化后应该为cnt[x+1] += cnt[x],cnt[x]=0
然后将所有未+1倍数的因子从set中删除，然后统计bei[facter[x+1]]，切记不要忘记清空bei[k]（因为当前已经处理，如果不清空会导致tle）
Code:
/*** keep hungry and calm PushyTao!***/ #pragma GCC optimize (2) #pragma G++ optimize (2) /** #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #define inline inline __attribute__( \ (always_inline, __gnu_inline__, __artificial__)) \ __attribute__((optimize("Ofast"))) __attribute__((target("sse"))) __attribute__((target("sse2"))) __attribute__((target("mmx"))) **/ #include <map> #include <set> #include <stack> #include <queue> #include <string> #include <vector> #include <math.h> #include <cstring> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; typedef long long ll; ll read() { ll c = getchar(), Nig = 1, x = 0; while (!isdigit(c) && c != '-')c = getchar(); if (c == '-')Nig = -1, c = getchar(); while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar(); return Nig * x; } #define read read() const int maxn = 6e5 + 3; int a[maxn], b[maxn]; vector<int> facter[maxn]; int mp[maxn]; set<int> bei[maxn]; //const int limit = 4e5 + 3; int main() { int n = read, m = read; for (int i = 1; i <= n; i++) a[i] = read; for (int i = 1; i <= m; i++) b[i] = read; // nlog for (int i = 2; i < maxn; i++) { for (int j = i; j < maxn; j += i) { facter[j].push_back(i);// j has a facter i } } for (int i = 1; i <= n; i++) { mp[a[i]] ++; if (mp[a[i]] == 1) { for (int yin : facter[a[i]]) { bei[yin].insert(a[i]);//every yin has a bei a[i] } } } ll ans = 0; for (register int i = 1; i <= m; i++) { int k = b[i];//cur k for (int beishu : bei[k]) {// the beishu of k ans += mp[beishu]; mp[beishu + 1] += mp[beishu]; mp[beishu] = 0;// all + 1 for (int yinzi : facter[beishu]) { if (yinzi != k) { bei[yinzi].erase(beishu);// delete beishu } } // beishu+1的因子是yinzi, yinzi的倍数是beishu+1 for (int yinzi : facter[beishu + 1]) { bei[yinzi].insert(beishu + 1); } } // clear bei[k].clear(); } cout << ans << endl; return 0; } /* */
