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

港控/mmm° 2022-11-21 11:44 122阅读 0赞

#### 异或 ####

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

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

输入描述:  
第一行两个整数n,q。  
接下来q行，每行两个整数 ki, vi。  
1 ≤ n, q ≤ 2×105  
1 ≤ ki, vi ≤ 109  
输出描述:  
输出共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(n2)

修正后代码

#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)。  
感觉复杂度并没有降低很多的样子…