ACwing刷题之基本算法（位运算）

a^b

求 a的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

0≤a,b≤10^9
1≤p≤10^9

输入样例：

3 2 7

输出样例：

思路

本题要利用快速幂的思想。如果按暴力求解，那么求解百万次，O(n)的时间复杂度超级大。所以我们不妨换一种思路去求解，用数学的思维来分析如何精简计算步骤。

拿5来举例。5^7可以被拆解成什么呢？

(5^1)(5^2)(5^4)

1->2^0,2->2^1,4->2^2…以此类推，

倘若此时我们要算5^1000000。

我们可以算到2^19时停止，2^20本身>=1000000(1024*1024>1000000)。先算完上面的20个数。。然后看1000000的二进制怎么表示。11110100001001000000。找到了二进制，我们就把二进制对应位置的5^i乘进去。(因为同底指数相乘幂相加)。此时时间复杂度变成了O(logn)级别。

下面是代码实现：

#include <iostream>
using namespace std;
int main(){
    int a, b, p;
    cin >> a >> b >> p;
    int res = 1%p;//先定义一个result。%p是为了防止测试数据模1.
    //从b的个位开始考虑
    while(b){
        if(b&1) res = res*1ll*a%p; //&代表位运算,ill是long long类型的，目的是强制转换防止溢出
        //不断地循环，要先把十位、百位、千位...准备好
        a = a*1ll*a%p;
        b >>= 1;//把个位去掉
    }
    cout << res << endl;
    return 0;
}

一些知识点的补充

位运算符作用于位，并逐位执行操作。&运算通常用于二进制取位操作，例如一个数 &1的结果就是取二进制的最末位。
a<<b 表示把a转为二进制后左移b位（在后面添加 b个0）。例如100的二进制表示为1100100，100左移2位后（后面加2个零）：1100100<<2 =110010000 =400。
和<<相似，a>>b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。
(a * b) % p = (a % p * b % p) % p

64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式

第一行输入整数a，第二行输入整数b，第三行输入整数p。

输出格式

输出一个整数，表示a*b mod p的值。

数据范围

1≤a,b,p≤10^18

输入样例：

1
2
3

3
4
5

输出样例：

思路

本题和上题思路相同，利用快速幂的思想进行求解。a*b实际上是b个a相加。那么可以将b转化成二进制，然后利用位运算进行求解。

代码如下：

#include <iostream>
using namespace std;
typedef unsigned long long ull;//因为64位很大

int main(){
    ull a,b,p;
    cin >> a >> b >> p;
    ull res = 0;
    while(b){
        if(b & 1)  res =(res+a)%p;
        a = a*2%p;
        b >>=1;//去位
    }
    cout << res;
    return 0;
}

最短Hamilton路径

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 n。

接下来 n 行每行 n 个整数，其中第 i行第 j 个整数表示点 i到 j的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x]并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

1≤n≤20
0≤a[i,j]≤10^7

输入样例：