位逻辑运算符——异或(^)

异或指的是参与运算的两个值,如果两个相应位(二进制形式下,按位运算)相同,则结果为0,否则为1。
我们先测试一下^的计算功能

#include<stdio.h>
int main()
{
    int a,b;
    while(~scanf("%d %d",&a,&b))
    {
        printf("%d\n",a^b);
    }
    return 0;
}
input:
0 0
0 1
1 0
1 1
output:
0
1
1
0

实例分析

HPUOJ 18级新生周赛第四场 A. 阴与阳

题目描述
阴与阳
单测试点时限: 1.0 秒

内存限制: 256 MB

“龟,象也;筮,数也。物生而后有象,象而后有滋,滋而后有数。” ——《左传·僖公十五年》

数,从诞生开始,就被赋予了特殊的意义。

从古希腊起,奇数就比偶数更招人喜爱。公元前6世纪的希腊哲学家毕达哥拉斯说,奇数阳刚(代表男性),偶数阴柔(代表女性)。他说,奇数拒绝被一分为二,说明它强大;偶数能被平分,说明它很脆弱。

在《周易》中,奇数代表阳爻,偶数代表阴爻。阳反而阴顺,故奇数刚而偶数柔。

而在当今素粒子领域的现象,似乎也认证了他们的见解:奇数的粒子的运动比偶数的粒子激烈。

现在定义阴数和阳数的概念:在一个无序序列中,出现次数为奇数次的数为阴数,出现次数为偶数次的数为阳数

输入
第一行输入一个奇数N (1≤N≤107+1)

第二行输入N个整数x (0≤x≤109)

输入数据有多组,输入到文件结束

保证每组输入数据一定有且仅有一个阴数

输出
输出每组数据中的唯一的阴数
样例
input

5
1 5 5 1 3
3
1 1 2

output

3
2

提示
本题输入输出量比较大,请尽量使用快速的OI方法。
题意分析
题目描述很多,但是我们需要的就是读取里面有用的信息供自己使用。题目中说出现次数为奇数次的数为阴数,出现次数为偶数次的数为阳数,并且保证每组数据有且只有一个阴数,也就是说把两个相同的数两两消去,最后剩下的数就是阴数,不好理解的话可以想象一下扑克牌中的抽老鳖游戏,最后剩下的那个数没有与它配对的就是老鳖,也就是这里的阴数。并且看到题目中的数据范围,直接暴力显然是不行的,这里就要用到我们的^了。
代码实现
首先我们来看一下多个数依次异或之后的结果

#include<stdio.h>
int main()
{
    int t,a,b;
    scanf("%d %d",&t,&a);
    t-=1;
    while(t--)
    {
        scanf("%d",&b);
        a=a^b;
    }
    printf("%d\n",a);
    return 0;
}
input:
5
1 1 2 2 3
5
1 1 2 2 2
3
1 3 1
output:
3
2
3

从这里你应该就可以看出异或的去重性,其实仔细想一下就很容易想到每两个相同的数异或之后为0,而0与任意一个数异或之后等于那个数,所以最后出现的数就是只出现过1+2n(奇数次)的数了。到了这里应该也可以发现,上面的代码加上多组输入就已经是本题的答案了,做简单的更改就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);//使流的输入输出速度与C的输入输出持平
    ll n,x,ans;
    while(cin>>n)
    {
        ans=0;
        while(n--)
        {
            cin>>x;
            ans^=x;
           }
        cout<<ans<<endl;
    }
    return 0;
}

之前的ac代码蜜汁TLE了,但是用上ios::sync_with_stdio(false)与cin和cout可以过,scanf和printf却过不了。
ios::sync_with_stdio(false):iostream默认是与stdio关联在一起的,以使两者同步,因此消耗了iostream不少性能,设置为false后,不再同步了,iostream的性能提高了很多倍。而cin,cout之所以效率低,是因为先把要输出的东西存入缓冲区,再输出,导致效率降低,而这段语句可以来打消iostream的输入输出缓存,可以节省许多时间,使效率与scanf与printf相差无几。本段话摘选自(https://blog.csdn.net/deepseazbw/article/details/76672177)

位逻辑运算符————与(&) 移位运算符————右移运算符(>>)实现快速幂

&运算通常用于二进制取位操作,例如一个数 &1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶,二进制的最末位为0表示该数是偶数,最末位为1表示该数为奇数
>>右移运算符,具体的用法书上和网站上总结的都有很多。快速幂也用到了这个运算符。
具体实现请参考在下的学习笔记中的快速幂实现。

实例分析

HDUOJ 1905 Pseudoprime numbers

题目描述
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description
Fermat’s theorem states that for any prime number p and for any integer a > 1, a^p == a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)
Given 2 < p ≤ 1,000,000,000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input
Input contains several test cases followed by a line containing “0 0”. Each test case consists of a line containing p and a.

Output
For each test case, output “yes” if p is a base-a pseudoprime; otherwise output “no”.

Sample Input
3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

Sample Output
no
no
yes
no
yes
yes
题意分析
英文题面虽然不太好读懂,但是这道题的题意还是很清晰的。就是给出两个数p,a,如果p是素数输出no,否则判断a的p次方对p取模之后是不是等于a,如果不是a输出no。表面看是挺无脑的,但是看到数据范围会发现直接求n次方是不行的,绝对会超时,这时就要用到快速幂了。
代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll isok(ll x)//判断是否为素数
{
    if(x<2)
        return 0;
    for(ll i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        {
            return 0;
        }
    }
    return 1;
}
ll poww(ll x,ll y,ll z)//快速幂
{
    ll ans=1,base=x;
    while(y!=0)
    {
        if(y&1!=0)
            ans=ans*base%z;
        base=(base%z)*(base%z)%z;
        y>>=1;
    }
    return ans;
}
int main()
{
    ll a,p;
    while(cin>>p>>a)
    {
        if(p==0&&a==0)
            break;
        if(isok(p))
            puts("no");
        else
        {
            ll s=poww(a,p,p);
            if(s%p==a)
                puts("yes");
            else
                puts("no");
        }
    }
    return 0;
}

除去快速幂,基本上可以算是一道水题了,看代码应该都是可以看懂的。