首页 > 代码库 > Acdream 1007 快速幂，模乘法

Acdream 1007 快速幂，模乘法

2024-07-17 15:18:06   220人阅读

http://acdream.info/problem?pid=1007

 

题目大意，给你n个数，输出这n个数的k次方的和，注意最后的结果得是正数。

刚开始因为模乘法没有考虑好，一直死wa不过，后来在模乘法中特判一下，终于ac了。

 

#include<cstdio>typedef long long LL;const LL MOD = 10000000007LL;int n;LL k, temp, sum;LL mul_mod(LL a, LL b){    LL res = 0;    int flag = (b < 0);    b = (b ^ (b >> 63)) - (b >> 63);    while(b)    {        if(b & 1)            res = (res + a) % MOD;        b >>= 1;        a = (a << 1) % MOD;    }    res %= MOD;    return (flag ? (~res + 1) : res);}LL calc(LL a, LL k){    LL res = 1;    while(k)    {        if(k & 1)            res = mul_mod(a, res) % MOD;        k >>= 1;        a = mul_mod(a, a) % MOD;    }    return res;}int main(){    int tCase;    scanf("%d", &tCase);    while(tCase--)    {        sum = 0;        scanf("%lld%lld", &n, &k);        for(int i = 0; i < n; ++ i)        {            scanf("%lld", &temp);            sum = (sum + calc(temp, k)) % MOD;        }        printf("%lld\n", (sum + MOD) % MOD);    }    return 0;}
View Code

 


联系
我们