[gym 102423]-elven efficiency | thinking

Topic link

The question ：
Given n Number a[i], Then there is m Number $k_{i}1\le i\le m$, For each of these k, Will this n There is no k The number of multiples of plus 1, A poll m Number , Ask the most operation times

Take the example ：
3 5
10
11
12
2
11
4
13
2

10 11 12
->2 Multiple yes 10、12 It becomes ： operation 2 Time
11 11 13
->11 Multiple yes 11、11 It becomes ： operation 2 Time
12 12 13
->4 Multiple yes 12、12 It becomes ： operation 2 Time
13 13 13
->13 Multiple yes 13、13、13 It becomes ： operation 3 Time
14 14 14
->2 Multiple yes 14、14、14 It becomes ： operation 3 Time
15 15 15
A total of operations are required 12 Time

Ideas ：
The original size is up to 3e5, If for m Each of the numbers , All are 3e5 Even +1 The factor of the next number , Should be increased , Up to 6e5
So you can filter 1-6e5 Each number factor , And save ,vector facter[x] Storage x What are the factors
And for m Number , If their multiples are a[i], Then we need to give a[i] Do one operation , Make a contribution to the answer
So the first time , We can count a[i] The number of occurrences of each number in , And record the corresponding a[i] Whose multiples （ I've got a[i] Factor of , Store in facter[a[i]] in ,a[i] The factor is x, that x A multiple of a[i], So we can make use of the pretreated facter[a[i]] obtain ）,facter[a[i]][j] Record for each factor , Then multiple set bei[facter[a[i]][j]] = a[i] It must be certain , So it can be found directly in the processing process bei[k[i]], For each of these k Multiple x, Contribution plus their number cnt[x], there cnt[] Preprocessing is required , And according to +1 Changes are counted again ：+1 After the change, it should be cnt[x+1] += cnt[x],cnt[x]=0
Then put all the non +1 The factor of the multiple is from set Delete in , Then count bei[facter[x+1]], Remember not to forget to empty bei[k]（ Because it has been processed , If it is not emptied, it will cause 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 What is the best factor yinzi, yinzi The multiple of is beishu+1
			for (int yinzi : facter[beishu + 1]) {
    
				bei[yinzi].insert(beishu + 1);
			}
		}
		// clear
		bei[k].clear();
	}
	cout << ans << endl;
	return 0;
}
/* */