龟速乘

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long c,sum = 0;
    cin>>n>>c;
    long long a[n];
    for(int i = 0 ; i < n ; i++){
        cin>>a[i];
        a[i] %= c;
    }
    for(int i = 1 ; i < n ; i++){
        while(a[i] > 0){
            if(a[i] & 1){
                sum = (sum % c + a[0] % c) % c;
            }
            a[0] = (a[0] % c + a[0] % c) % c;
            a[i] = a[i] / 2;
        }
        a[0] = sum;
        sum = 0;
    }
    cout<<a[0]<<endl;
    return 0;
}

跟快速幂的思想差不多: 首先假设a * b mod p;

第一步: 将b进行二进制分解得到(2^0 + 2^1 + 2^3.....) 所以: a * b = a * 2^0 + a *2^1.......; 我们发现后一项是前一项的2倍,因此我们只需要判断b的二进制为是否是1,如果是,就加,不是就不加,然后,得到两个数的乘积后得到一个数,和第三个数继续做上面的操作.

写的不是很清楚

#include <algorithm>
using namespace std;

const int N = 110;
long long ans[N];
int n;
long long p;
int main()
{
    scanf("%d%ld", &n, &p);
    for(int i = 1; i <= n; i++) scanf("%lld", &ans[i]);

    long long res = 0;
    long long temp  = ans[1];
    for(int i = 2; i <= n; i++)
    {
        long long a = temp;
        long long b = ans[i];
        while(b)
        {
            if(b & 1) res = (long long) (res + a) % p;
            b >>= 1;
            a = (long long)(a * 2) % p;
        }
        if(i != n)
        {
            temp = res;
            res = 0;
        }
    }
    printf("%lld", res);
}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[100],ans,c;

ll quick_mul(ll a, ll b, ll c) {

ll ans = 0;
a %= c;//大数先模一下
b %= c;
while (b) {
	if (b & 1) ans = (ans +a)%c;
	a = (a%c + a%c)%c;//大数需要同余注意,原型：(a+a)%c
	b >>= 1;
}
return ans%c;

}

int main() { int n;

ans = 1;

cin >> n >> c;

for (int i = 0; i < n; i++) {

	cin >> a[i];

	ans = quick_mul(ans, a[i],c);

}

cout << ans;

return 0;

}