Codeforces 424C Magic Formulas

秒速五厘米 2022-08-18 11:49 12阅读 0赞

题目链接：\[这里写链接内容\] ([http://codeforces.com/contest/424/problem/C][http_codeforces.com_contest_424_problem_C])  
题面：  
C. Magic Formulas（神奇的矩阵）  
time limit per test2 seconds  
memory limit per test256 megabytes  
inputstandard input  
outputstandard output

People in the Tomskaya region like magic formulas very much. You can see some of them below.

Imagine you are given a sequence of positive integer numbers p1, p2, …, pn. Lets write down some magic formulas:  
![这里写图片描述][e57fbbf0c16d0964970e5e17787053a093edf790.png]  
![这里写图片描述][6bb804f17c2d69abd667c23a5dd2b0277164b8b6.png]

Here, “mod” means the operation of taking the residue after dividing.

The expression means applying the bitwise xor (excluding “OR”) operation to integers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by “^”, in Pascal — by “xor”.

People in the Tomskaya region like magic formulas very much, but they don’t like to calculate them! Therefore you are given the sequence p, calculate the value of Q.

Input  
The first line of the input contains the only integer n (1 ≤ n ≤ 106). The next line contains n integers: p1, p2, …, pn (0 ≤ pi ≤ 2·109).

Output  
The only line of output should contain a single integer — the value of Q.

Sample test(s)  
input  
3  
1 2 3  
output  
3

言简意赅：按照上述公式求解最后的数值Q，由于时间受限所以暴力并不能AC，根据题目提示Magic Formulas，可以知道要写出一个矩阵，找到规律并实现。  
注意：异或运算是满足交换律的，0异或X的值即为X，可以把原来的值在输入时即完成异或，之后的求余运算可以写到矩阵里面，找到规律对总个数中i的个数进行判断奇偶。

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    int p[1000005];
    int main()
    {
        int n;
        int Q;
        int i,j;
        while(scanf("%d",&n)!=EOF)
        {
            Q=0;
            for(i=1;i<=n;i++)
            {
                scanf("%d",&p[i]);
                Q^=p[i];
            }
            //cout<<Q<<endl;
            p[0]=0;
            p[1]=0;
            for(int i=2;i<=n;i++)
            {
                p[i]=p[i-1]^(i-1);
            }
            for(int i=1;i<=n;i++)
            {
                int count=n/i;
                int yu=n%i;
                if(count&1)
                Q^=p[i];
                Q^=p[yu];
               // Q^=0;
                Q^=yu;
            }
            printf("%d\n",Q);
        }
        return 0;
    }

[http_codeforces.com_contest_424_problem_C]: http://codeforces.com/contest/424/problem/C
[e57fbbf0c16d0964970e5e17787053a093edf790.png]: /images/20220731/ab82d0fe735643d8ae0dfaab82e78b6c.png
[6bb804f17c2d69abd667c23a5dd2b0277164b8b6.png]: /images/20220731/4e182a89f8ce4221b83d0ffdfd0ed9fd.png