经典位运算-- a^b%p 和 64位乘法

亦凉 2022-03-20 03:13 242阅读 0赞

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

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

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

**数据范围  
1≤a,b,p≤10^9**

**时/空限制： 1s / 32MB**

**输入样例：**  
3 2 7  
**输出样例：**  
2

**解题思路：**  
按照我们正常的思路去想就是a一共累乘b次，这样做的时间复杂度是O(b), 但是这个问题是可以优化到 lg(b) 级别的。下面我们拿一个例子说明：  
例如 求 5 ^ 7:  
对于一个数我们可以把数写成10进制数累加的形式，如756 = 7 \* 100 + 5 \* 10 + 6， 同样的也可以写成2进制数累加的形式，如 7 = 4 + 2 + 1，那么 5^7 = 5^(4 + 2 + 1) = 5^4 \* 5^2 \* 5^1, 这就是优化的思路，之前我们需要计算 b次，而优化后 我们只需要计算lg(b)次，降了一个数量级。  
**计算机是个实践科学，知道思路后和写出代码还有不小的一段距离，希望大家仔细看看代码解决其他的一些细节问题吧。**

**详细代码：**

#include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    
    using namespace std;
    
    typedef long long ll;
    
    ll getan(ll a,ll n,ll p)
    {
        
        if(!n)
            return 1 % p;
        ll res = 1;
        ll ap = a;
        while(n)
        {
        
            if(n & 1){
        
                res = (res * ap) % p;
            }
            n = n >> 1;
            ap = (ap * ap) % p;
        }
        return res;
    }
    /*126348976 982638476 938420413*/
    int main()
    {
        
        ll a,n,p;
        cin >> a >> n >> p;
        cout << getan(a,n,p) << endl;
    }

## 2. 64位整数乘法 ##

**求 a 乘 b 对 p 取模的值。**

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

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

**数据范围  
1≤a,b,p≤10^18**

**时/空限制： 1s / 32MB**

**输入样例：**  
3  
4  
5  
**输出样例：**  
2

**解题思路：**  
我们可以看到a,b的数据范围是很大的，所以直接a \* b % p的做法一定回溢出，当然出题人也不会这么\*\*，a \* b 会溢出但是a + a 不会溢出啊，所以直观想到就是把a累加b次，这样做的时间复杂度是O(b)的，b的最大值是10^18，O(n)的做法一定会超时，所以我们需要一个lg级别的做法，这时候/坏笑，大家可能会观察到和上一题的类似之处，上一题是累乘b次，这一题是累加b次，没错，优化思路和上一题一样，把b写成用二进制表示的形式，这样只需要累加lg(b)次。  
上代码！

**详细代码：**

#include <iostream>
    
    using namespace std;
    
    typedef long long ll;
    
    int main()
    {
        
        ll a, b, p;
        cin >> a >> b >> p;
        ll res = 0;
        while(a)
        {
        
            if(a & 1){
        
                res = (res + b) % p;
            }
            a = a >> 1;
            b = 2 * b % p;
        }
        cout << res << endl;
        return 0;
    }