异或

Problem

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

给出q次操作，每次操作之后输出序列的异或和，并且在操作结束之后输出整个序列。

序列的异或和为

Input

第一行两个整数n,q。

接下来q行，每行两个整数

Output

输出共q+1行，其中前q行每行一个整数，为每次操作结束后的序列的异或和。

最后一行为操作结束后的序列。

思路

蒟蒻开始的想法当然是暴力了，不过想到每次都要输出整个序列的异或和就能稍微优化一下
因为对于每个 ，都有 (mk <= n)和 异或，所以只要判断m的奇偶性就知道当前异或和（m为奇数就是i-1时异或和异或V，m为偶数就和上一次i结果相同）

所以刚开始蒟蒻的想法是这样的：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll a[200005];
int main() {
    ll n = read(), Q = read();
    ll ans = 0;
    for (int i = 1; i <= Q; ++i) {//1到Q次运算
        int k = read(), v = read();
        for (int j = k; j <= n; j += k) { // 每次运算都对数组a进行异或
            a[j] ^= v;
        }
        if ((n / k)& 1) ans ^= v; // n/k 为数组中与V异或的数量
        cout<<ans<<endl;
    }
    for (int i = 1; i <= n; ++i) {
        cout << a[i] << " ";
    }
    return 0;
}

当然果断的TLE了，复杂度

后来想到要计算的只是最后的a数组各数的大小，不需要计算出中间值

因为对于每个k，都能确定是那些ai要与对应的V异或，利用前缀和的思想，我们在开始只让 与V异或，当遍历完后再从an到a1依次让

所以代码就变成：

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll a[200005];
int main() {
    ll n = read(), Q = read();
    ll ans = 0;
    for (int i = 1; i <= Q; ++i) {
        int k = read(), v = read();
        if(k <= n) a[k] ^= v;
        if ((n / k) & 1) ans ^= v;
        printf("%lld\n",ans);
    }
    for (int i = n; i >= 1; --i) {
       if(a[i]){
           for(int j = 2*i ; j <= n ; j+=i) a[j] ^= a[i];
       }
    }
    for(int i = 1 ; i <= n ; ++i){
        printf("%lld ",a[i]);
    }
    return 0;
}