怎样做好网站,wordpress搜索结果不存在页面,怎么创建自己的网站平台app,儿童摄影网站怎么做文章目录 QuestionIdeasCode Question
给定一个长度为 n 的非负整数序列 a1,a2,…,an 。
对于 1≤i≤n #xff0c;有 biai⊕(imod1)⊕(imod2)⊕…⊕(imodn) 。
请你计算并输出 b1⊕b2⊕…⊕bn 的值。
⊕ 表示按位异或。
输入格式 第一行包含整数 n 。
第二行包含 n 个整… 文章目录 QuestionIdeasCode Question
给定一个长度为 n 的非负整数序列 a1,a2,…,an 。
对于 1≤i≤n 有 biai⊕(imod1)⊕(imod2)⊕…⊕(imodn) 。
请你计算并输出 b1⊕b2⊕…⊕bn 的值。
⊕ 表示按位异或。
输入格式 第一行包含整数 n 。
第二行包含 n 个整数 a1,a2,…,an 。
输出格式 一个整数表示 b1⊕b2⊕…⊕bn 的值。
数据范围 前 3 个测试点满足 1≤n≤3 。 所有测试点满足 1≤n≤106 0≤ai≤2×109 。
输入样例 3 1 2 3 输出样例 3
Ideas
Code
// 时间复杂度需要控制在ON或者Onlgn)
// 将计算结果的矩阵写出来尝试找规律发现竖着有规律
// 规律为第一列取模结果均为0000第二列为0101第三列为0120...以此循环
// 根据异或运算的性质交换律、X^X0可以得出如果循环序列循环k次k为偶数就等于0
// 所以只需要判断k是否奇数还需要处理循环序列的最后的部分最后一个元素为n%i(i为列号)
// 可以预处理一个前缀和数组s[i],表示1^2...^n; s[0] 0
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1000010;int n;
int s[N];int main()
{scanf(%d, n);for (int i 1; i n; i ) s[i] s[i - 1] ^ i;int res 0;for (int i 0; i n; i ){int a;scanf(%d, a);res ^ a;}for (int i 1; i n; i ){int k n / i; if (k 1) res ^ s[i - 1];res ^ s[n % i];}printf(%d\n, res);return 0;
}
