ACdream 1007 a+b 快速幂 java秒啊,快速幂 避免 负数移位出错

 1 import java.util.*;

 2 import java.math.*;

 3 import java.io.*;

 4 public class Main

 5 {

 6     static BigInteger mod=new BigInteger("10000000007");

 7     public static void main(String[] args)

 8     {

 9         // 对于大量输入，下面方式可能会快一些。

10         Scanner cin=new Scanner(new BufferedInputStream(System.in));

11         int T,n;

12         BigInteger k,sum,x;

13         T=cin.nextInt();

14         while(T-->0)

15         {

16             n=cin.nextInt();

17             k=cin.nextBigInteger();

18             sum=BigInteger.ZERO;

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

20             {

21                 x=cin.nextBigInteger();

22                 sum=sum.add(x.modPow(k,mod)).mod(mod);

23             }

24             System.out.println(sum);

25         }

26         cin.close();

27     }

28 }

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <cmath>

 5 #include <algorithm>

 6 #include <string>

 7 #include <vector>

 8 #include <set>

 9 #include <map>

10 #include <stack>

11 #include <queue>

12 #include <sstream>

13 #include <iomanip>

14 using namespace std;

15 typedef long long LL;

16 const int INF = 0x4fffffff;

17 const double EXP = 1e-5;

18 const int MS = 1005;

19 const int SIZE = 100005;

20 const LL mod=10000000007;

21

22 LL mul_mod(LL x,LL n)

23 {

24       x%=mod;

25       LL res=0;

26       while(n)

27       {

28             if(n&(1LL))

29             {

30                   res=(res+x)%mod;

31             }

32             x=((x<<1LL)%mod);    // 千万注意，当x为负数的时候，会出错。需要转正

33             n>>=1LL;

34       }

35       return res;

36 }

37

38

39 LL pow_mod(LL x,LL n)

40 {

41       LL res=1LL;

42       x%=mod;

43       while(n)

44       {

45             if(n&(1LL))

46                  // res=res*x%mod;

47                  res=mul_mod(res,x);

48            // x=x*x%mod;

49            x=mul_mod(x,x);

50             n>>=1LL;

51       }

52       return res;

53 }

54

55 int main()

56 {

57       LL T;

58       LL n,k;

59       scanf("%lld",&T);

60       while(T--)

61       {

62             scanf("%lld%lld",&n,&k);

63             LL ans=0LL,x;

64             for(LL i=0;i<n;i++)

65             {

66                   scanf("%lld",&x);

67                   if(x>=0)

68                         ans=(pow_mod(x,k)+ans)%mod;

69                   else

70                   {

71                         if(k%2==0)

72                               ans=(pow_mod(-x,k)+ans)%mod;

73                         else

74                               ans=(-pow_mod(-x,k)+ans)%mod;

75                   }

76             }

77             printf("%lld\n",(ans+mod)%mod);

78       }

79       return 0;

80 }