基础算法题——异或（复杂度的小差异）

异或

题目描述
给定一个长度为 n 初始全为 0 的数列 a_i，下标从 1 开始。定义操作模 k 异或 v 为对所有满足 k_i≡0(mod k) 的下标 i，将异或上整数v（即令 a_i = a_i⊕v）。

给出q次操作，每次操作之后输出序列的异或和，并且在操作结束之后输出整个序列。
序列的异或和为 a ₁⊕a ₂⊕…⊕a_n

输入描述:
第一行两个整数n,q。
接下来q行，每行两个整数 ki, vi。
1 ≤ n, q ≤ 2×10⁵
1 ≤ k_i, v_i ≤ 10⁹
输出描述:
输出共q+1行，其中前q行每行一个整数，为每次操作结束后的序列的异或和。
最后一行为操作结束后的序列。
示例1
输入
10 3
1 1
2 2
3 4
输出
0
2
6
1 3 5 3 1 7 1 3 5 3
备注:
i ≡ 0(modk) 等价于 i mod k = 0

求余知识点：
a ^ k = a ^ k ^ k ^ k
a = a ^ k ^ k

按照题目要求，写下如下代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int arr[200010];

int main(){
	int n, q;
	memset(arr, 0, sizeof(arr));
	scanf("%d%d", &n, &q);
	ll sum=0;
	for(int i=1; i<=q; i++){
		ll k, v;
		scanf("%d%d", &k, &v);
		for(int j=1; j<=n/k; j++)
			arr[j*k] = arr[j*k]^v;
		if(n/k%2)
			sum = sum^v;
		printf("%lld\n", sum);
	}
	
	for(int i=1; i<=n; i++){
		printf("%lld", arr[i]);
		if(i!=n) printf(" ");
	}
	
	return 0;
} 

复杂度为 O(n²)

修正后代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int arr[200010], ans[200010], n;

int main(){
	int q;
	memset(arr, 0, sizeof(arr));
	scanf("%d%d", &n, &q);
	ll sum=0;
	for(int i=1; i<=q; i++){
		ll k, v;
		scanf("%d%d", &k, &v);
		if(n>=k){
			arr[k] = arr[k]^v;
			if(n/k%2) sum = sum^v;
		}
		printf("%lld\n", sum);
	}
	
	for(int i=n; i>=1; i--){
		for(int j=i; j<=n; j+=i){
			ans[j] ^= arr[i];
		}
	}
	for(int i=1; i<=n; i++){
		printf("%d", ans[i]);
		if(i!=n)
			printf(" ");
	}
	
	return 0;
} 

复杂度为O( a*b )，其中(a+b=n)。
感觉复杂度并没有降低很多的样子…