从零开始学算法-Day2

//2020.4.21 学习算法的第二天

题目：Raising Modulo Numbers

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

题目描述：就是求多组数据的幂之和 对 M 求模。

求解之路：

有了昨天的经验，这个就是水题了，无非是对数据的处理。

#include <iostream>

using namespace std;
typedef long long LL;

int fast_pow(LL a,LL b,LL M){
    LL result = 1 % M;
    while(b){
        if(b & 1)
            result = result * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return result;
}
int main(){
    int z;//数据的组数
    int m;//被模取得数
    int n,a,b;//记录每组数据
    cin >> z;
    while(z--){
        int count = 0;
        cin >> m >> n;
        while(n--){
            cin >> a >> b;
            count = (count + fast_pow(a,b,m)) % m;;
        }
        cout << count <<endl;
    }
    return 0;

}

一次通过。耶耶耶！！！！

今天当然不能就这么算了啊，太糊弄人了。哈哈哈哈哈
---------------------我是分割线------------------------

题目:64位整数乘法

题目描述:求 a 乘 b 对 p 取模的值，其中1≤a,b,p≤10^18

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

涉及知识点:有取模大数相乘

求解之路:

这个嘛就跟昨天类似的思路嘛,直接乘数据肯定得溢出,那我们就分开乘啊,怎么分呢?
但是还是用位运算啊,这个简单嘛.还好用!
但是这和求幂还不一样,求幂是相乘,两个数分开乘,最后当然是相加啦!!!

#include <iostream>
using namespace std;
typedef long long LL;

LL fuc(LL a,LL b,LL c){
    LL result = 0;
    while(b){
        if(b & 1)
            result = (result + a) % c;
        b >>= 1;
        a = a * 2 % c;
    }
    return result % c;
}
int main (){
    LL a,b,c;
    cin >> a >> b >> c;
    cout << fuc(a,b,c);
    return 0;
}

结果当然也是

哈哈哈哈!!!!

总结:我们在遇到这种有模取得乘法,一定不能想着直接就去乘,因为数据很容易就溢出了,所以位运算真好用.哈哈哈哈,当然啦,在实际得运用中细节也是很重要的,就像我的函数开始用的int,直接所有数据不通过,所以啊,还是得考虑周全.