一、 快速幂

请你计算 a^b mod p 的值。
一共有 q 次询问。
输入描述：
第一行输入一个正整数 q，代表询问次数。
接下来每行输入三个正整数 a,b,p，代表一次询问。
数据范围：
1≤q≤10 ^5

1≤a,b,p≤10 ^7

输出描述：
对于每次询问，输出一个整数，代表 a^b mod p 的值。

解法:

根据公式 (a1*a2)^b %p = (a1%p)^b * (a2%p)^b %p可以进行快速幂计算
本题不可直接计算，否则数据溢出

#include
using namespace std;
long long quickpow(long long a,long long b,long long p)
{
    long long res=1;
    while(b)
    {
        if(b&1)//如果b为奇数
            res=res*a%p;
        a=a*a%p;
        b>>=1;//相当于除2
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        long long a,b,q;
        cin>>a>>b>>q;
        cout<<quickpow(a, b, q)<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

二、快速乘

请你计算 a∗b mod p 的值。要求只能使用加法和取模运算，且计算过程中的值不能超过 2*10^7
一共有 q 次询问。
输入描述：
第一行输入一个正整数 q ，代表询问次数。
接下来每行输入三个正整数 a,b,p，代表一次询问。
数据范围：
1≤q≤10^5

1≤a,b,p≤10^7

输出描述：
对于每次询问，输出一个整数，代表a∗b mod p 的值。

解法一:

(a+b%p=(a%p+b%p)%p
(a-b)%p=(a%p-b%p)%p
(ab)%p=(a%pb%p)%p

#include
using namespace std;
int main()
{
    long long a,b,p;
    int n;
    cin>>n;
    while(n--)
    {
        cin>>a>>b>>p;
        long long k=0;//定义储存变量
        while(b--)
            k+=a%p;//累加
        cout<<k%p<<endl;//总和取模
        k=0;//归0
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解法二:

用一般方法通过了，数据未越界，但快速幂越界

#include
using namespace std;
int main()
{
    long long a,b,p;
    int n;
    cin>>n;
    while(n--)
    {
        cin>>a>>b>>p;
        cout<<a*b%p<<endl;//总和取模
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15