从零开始学算法-Day1

/*小声唠叨一下
Markdown这个链接方式不会用，
明明和说明文档一样的
委屈😔
*/

那就开始正题了

---------------------我是分割线------------------------

//2020.4.20 算法学习第一天，希望自己能坚持下来

题目：a^b

题目描述：求 a 的 b 次方对 p 取模的值，其中​0≤a,b,p≤10^9

链接：https://ac.nowcoder.com/acm/contest/996/A
来源：牛客网

涉及知识点：快速幂、位运算

求解之路：

---------------------Round 1------------------------

#include <iostream>
using namespace std;
int pow1(int x,int n,int p){
    long long result = 1 % p;
    while(n--){
        result *= x;
        result %= p;
    }
    return result;
}
int main(){
    int numa,numb,numc;
    cin >> numa >> numb >> numc;
    cout << pow1(numa,numb,numc)<<endl;
    return 0;
}

结果嘛，emmm

有点意思。
超时了，就是因为方法太简单，循环太多了。
所以一个解决办法就是将每次乘积的次数缩小，我们就想到了一个方法，转化成多个结果乘积在一起，例如
2^5 = 2^(2+3) = 2^2 * 2^3,循环乘积一下子就变成了3次，比直接循环5次节约太多时间了，但是这样不能确定每一次指数到底怎么简化。
所以更好的办法是将指数转化成二进制数，例如2^5 = 2^101 = 2^(1 * 2^2+0 * 2^1+1 * 2^0)。
这样就有一个标准了。


---------------------Round 2------------------------

#include <iostream>
using namespace std;
int pow1(int x,int n,int p){
    long long  result = 1 % p;
    while(n){
        if(n&1)
            result = result * x % p;
        x = x * (long long)x % p;
        n >>= 1;
    }
    return result;
}
int main(){
    int numa,numb,numc;
    cin >> numa >> numb >> numc;
    cout << pow1(numa,numb,numc)<<endl;
    return 0;
}

铛铛铛~

总结：

1. 首先我们在做题的时候。不能想着直接暴力求解，应该注意去优化代码，不然超时真的不让过啊
2. 我们在做题的时候真的要考虑全面啊，例如：当 n = 0，p = 1的时候，我们如果不去做处理，结果一样的不对啊。
3. 数据类型也很重要啊，题目给的数很大，如果不用long long 申明就必须去强制转化，或者直接声明long long 类型的所有数据，不然错误原因都找不到啊。
4. 位运算真好用。

补充：

位运算的相关知识：链接： https://blog.csdn.net/wildand/article/details/89377466