dreamstart 的催促

序号：

#120难度：困难时间限制：1000ms内存限制：10M

描述

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

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

输入

 

第 1 个数字为整数n，1<=n<=10^5

余下 n 个数，每个数的大小不超过10^15

 

输出

 

输出取模之后的和

 

输入样例

4 1 6 9 12

输出样例

3776019

 

 快速幂取摸加欧拉降幂

指数爆炸的时候就要降幂

就是求a^b mod c

可以转化为

a^(b mod phi(c)+phi(c)) mod c

phi 为 欧拉函数

1 #include
        
          2 #define LL long long 3 #define mod 4218984 4 using namespace std; 5 const int MAXN = 1e5+10; 6 const int MOd = 10000019; 7  8 LL a[MAXN]; 9 int n;10 // ll phi( ll n ) { //欧拉函数11 //     ll ans = n;12 //     for( ll i = 2; i*i <= n; i ++ ) {13 //         if( n%i == 0 ) {14 //             ans -= ans/i;15 //             while( n%i == 0 ) {16 //                 n /= i;17 //             }18 //         }19 //     }20 //     if( n > 1 ) {21 //         ans -= ans/n;22 //     }23 //     return ans;24 // }25 26 LL quick(LL a,LL x, LL MOD){27     LL r = 1;28     while(x>0){29         if (x&1){30             r = (r*a)%MOD;31             x--;32         }33         a = a%MOD*a%MOD;34         x>>=1;35     }36     return r%MOD;37 }38 39 int main(){40     scanf("%d",&n);41     for (int i = 0;i