A.dreamstart的催促

题目描述

有一天集训队的学弟们正在计算一堆数，但是dreamstart感觉他们算的太慢了，就让他们坐在一起想出一个快速计算的方法，但是由于他们一时想不出来，想让你帮助他们。他们说现在有一个数列，要算出第 i 个数的 i 次幂并且把每个数计算出来的值加到一起，最后答案模10000019。

聪明的你可以帮助他们吗？

输入描述

第一行有一个整数n，n <= 1e5
接下来一行有n个数，每个数的大小不超过1e16

输出描述

输出取模之后的和

思路

快速幂取模运算

 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 using namespace std;
 4 const int MAXN = 1e5+10;
 5 const int MOD = 10000019;
 6 LL a[MAXN];
 7 int n;
 8 
 9 
10 LL quick(LL a,LL x)
11 {
12     LL r = 1;
13     while(x>0)
14     {
15         if (x&1)
16         {
17             r = (r*a)%MOD;
18             x--;
19         }
20         a = a%MOD*a%MOD;
21         x>>=1;
22     }
23     return r%MOD;
24 }
25 
26 int main()
27 {
28     scanf("%d",&n);
29     for (int i = 0;i<n;i++)
30         scanf("%lld",&a[i]);
31     LL sum = 0;
32     for (int i = 0;i<n;i++)
33         sum = (sum + quick(a[i],i+1))%MOD;
34     printf("%lld
",sum);
35 
36     return 0;
37 }