把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

牛客14648 序列
有两个序列a,b(1e5)，数字大小<=序列长度，求有多少对x,y满足gcd(x,y)=1且a[b[x]]=b[a[y]]。

解：

很容易让人联想到反演的板子题，但是本题还有一个限定条件，不过本质还是通过反演把不定的gcd转化为有规律的筛法，问题转化为对于每个i，求得a[b[x]]=b[a[y]]的对数，其中x和y都是i的倍数。
这个东西好像确实是有点麻烦……整理一下，由于选择了筛法的做法，也就是先枚举i，然后再枚举i的倍数，复杂度大约在1e6，这个时候实际上i的倍数x和y之间是没有联系的，只要他们都是i的倍数就行，那么我们可以直接分开枚举，只要使得x和y满足条件即可。而满足条件的对数则是存在x,y为i的倍数使得a[b[x]]=b[a[y]]的对数。由于使用分开处理的思想，这里大可以先求出所有不同的a[b[x]]的个数，存入map，然后遍历b[a[x]]即可，x的选择和y的选择完全无关，通过这1e6的复杂度就可以处理出f(i)-对于i来讲，x,y是i的倍数时的对数。
然后直接反演求g(1)就行了。
算是比板子题灵活一点的板子题吧，还考到了数组存在性的问题，整体不是很难。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 14000005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
bool is_prime[100001] = { 1,1 };
int prime[100001];
int mu[100001];
int getmu(int n) {
	mu[1] = 1;
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		if (!is_prime[i]) {
			prime[++cnt] = i;
			mu[i] = -1;
		}
		for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
			is_prime[i * prime[j]] = 1;
			if (i % prime[j] == 0) { mu[i * prime[j]] = 0; break; }
			else mu[i * prime[j]] = -mu[i];
		}
	}
	return cnt;
}
ll part[maxn],a[maxn],b[maxn];
map<int, int> nums;
int main() {
	cfast;
//	cout << "okinit";
	getmu(100000);
	ll n;
	cin >> n;
	inc(i, 1, n + 1) {
		cin >> a[i];
	}
	inc(i, 1, n + 1) {
		cin >> b[i];
	}
	inc(i, 1, n + 1) {
		nums.clear();
		for (int j = i; j <= n; j += i) {
			nums[a[b[j]]]++;
		}
		for (int j = i; j <= n; j += i) {
		//	if (nums[b[a[j]]] > 0) {
				part[i] += nums[b[a[j]]];
		//	}
		}
	}
	ll ans = 0;
	inc(i, 1, n + 1) {
		ans += (ll)mu[i] * part[i];
	}
	cout << ans << endl;
}
/*

*/