位运算，快速幂

前景提要：模运算（mod）

注意：有关取模运算，n%mod—>若n>abs(mod)则n%mod=0;

//加法取模
(a+b)%mod=(a%mod+b%mod)%mod;
//乘法取模
(a*b)%mod=(a%mod*b%mod)%mod;
//减法取模
(a-b)%mod=(a%mod-b%mod+mod)%mod;
//除法取模（特殊）
//规则1：当a能整除b时
(a/b)%mod=a%(b*mod)/b;
//规则2：无论a是否可以整除b，当b和mod互质（b和mod很少不互质） or a不能整除b
(a/b)%mod=a*qp(b,mod-2,mod)%mod;

1.快速幂

一般的，形如求a的b次方mod c的式子，当b比较小的时候，通常可以使用暴力解决：

long long a,a1,b,c;
cin>>a>>b>>c;
a1=a;
for(int i=1;i<=b;i++)
{
    a*=a1;
    a%=c;
}
cout<<a;

时间复杂度是O（N）

然而快速幂的出现能够更加快速解决以上问题（利用二进制）

2.龟速乘，快速乘

一般使用到龟速乘是为了防止大数快速幂计算时防止超ll范围

模板：

typedef long long int ll;

//龟速乘模板
ll qp_mul(ll x,ll y,ll mod)
{
    ll ans=0;
    while(y!=0)
    {
        if(y&1)//y如果是奇数
        {
            ans+=x,ans%=mod;
        }
        x+=x,x%=mod;
        y>>=1;// y/=2;
    }
    return ans;
}

//快速幂模板
ll qp(ll x,ll y,ll mod)
{
    ll sum=1;
    while(y!=0)
    {
        if(y&1)
        {
            //sum*=sum;
            sum=qp_mul(sum,x,mod),sum%=mod;
        }
        //x*=x;
        x=qp_mul(x,x,mod),x%=mod;
        y>>=1;
    }
    return sum;
}


//快速乘
cin>>a>>b>>mod;
cout<<((a*b-(long long)((long double)a*b/mod)*mod+mod)%mod);
//速度O（1），不过数值过大时容易造成误差，毕竟long double转换时会有精度上的误差

最后总结一下，

1，快速幂——快速计算abmodc的式子，效率O（logN）

2，龟速乘——常与快速幂搭配使用，应对数据相乘会爆long long的情况

3，快速乘——巧妙利用long double，同样为了应对爆long long

3.题单#1

做23-24(1)第5次线上赛第6题，得知一个做位运算无敌的方法：真值表，直接get

题目：位运算23~24(1)-2

描述
已知两个无符号整数（unsigned int）a、b，现在需要求一个无符号整数c，使得(a & c) | (b ^ c)的值尽可能小。如果有多个c都满足条件，选其中最小的。
输入
这是一道多组案例的题目。一个正整数n，表示案例的数量。（n<=1000）每组案例由3个无符号整数a、b、c组成。（0<=a、b<=1亿）
输出
针对每组案例，输出一个无符号整数c，使得(a & c) | (b ^ c)的值尽可能小。如果有多个c都满足条件，输出其中最小的。每组案例输出完都要换行。
样例输入复制样例
2 10 2 3 5
样例输出
0 4

对于类似给你一串(a&c)|(b^c)的东西，先列一个真值表：

a	b	c	a&c	b^c	(a&c)|(b^c)
1	0	0	0	0	0
1	0	1	1	1	1
1	1	0	0	1	1
1	1	1	1	0	1
0	0	0	0	0	0
0	0	1	0	1	1
0	1	1	0	0	0
0	1	0	0	1	1

怎么看呢？好问题，因为c是我们自己填的数，所以看a,b一样的一组。

根据题目描述，找最小值且要找c小的，那就先看最后ans选最小的(选0)，如果一样就选取c最小的(c=0)的这一组作为后面判断的条件。

根据我们每组找到的a和b以及c后，就可以开始根据二进制拼c啦

完整代码：

n=int(input())
while n>0:
    n-=1
    a,b=map(int,input().split())
    a_=bin(a)[2:]
    b_=bin(b)[2:]
    b_ = '0' * (abs(len(a_) - len(b_))) + b_
    a_ = '0' * (abs(len(a_) - len(b_))) + a_
    c_=""
    for i in range(len(a_)):
        if a_[i]=='1' and b_[i]=='0':
            c_='0' + c_
        elif a_[i]=='1' and b_[i]=='1':
            c_='0' + c_
        elif a_[i]=='0' and b_[i]=='0':
            c_='0' + c_
        elif a_[i]=='0' and b_[i]=='1':
            c_='1' + c_
    c_=c_[::-1]
    print(int(c_,2))

快乐位运算

已知两个正整数 A 和 B，你需要找到一个非负整数 C 使得 (A | C) ^ (B & C) 的值尽可能小，由于这样的 C 可能会有很多，所以你只要输出满足要求的最小的 C 就可以。

》》(a&b)

快乐位运算-2

罗少在做位运算的时候发现了这样一种现象：两个正整数 a、b 在某些情况下满足 a | b = a ^ b

现在罗少想问问大家，在 1 ~ n 之间存在多少个 x 满足 x | n = x ^ n

例：

1 | 4 = 1 ^ 4 = 5

2 | 4 = 2 ^ 4 = 6

3 | 4 = 3 ^ 4 = 7

ll n;
cin >> n;
ll cnt = 0;
while (n > 0)
{
    if (!(n & 1)) cnt++;
    n >>= 1;
}
cout << (ll(1)<<cnt) - 1 << endl;

数列求和

现在有一个数列：1、4、9、16、25、36…

求这个数列的前n项和%1000000007的结果。

解题方法：平方和公式：n(n+1)(2*n+1)/6

快乐位运算-4

判断是否存在两个非负整数 a 和 b 满足 a + b = x，a & b = y。

ll x, y;
cin >> x >> y;
if (y > x)cout << "NO" << endl;
else
{
    ll z = x - y;
    if ((y & z) == y)cout << "YES" << endl;
    else cout << "NO" << endl;
}