校赛A题&&快速幂模板

2019-04-14 20:22发布

站内文章 / 模拟电子
11326 0 1681
网址如下：
https://ac.nowcoder.com/acm/contest/339/A?&headNav=acm
首先从题目看出来这是一道算法签到题———快速幂
题目主要是考察对快速幂算法的熟悉程度
需要注意的是：题目要求我们答案模10000019，所以如果不模，会报wa，这是需要注意的地方 #include #include using namespace std; const int maxn = 1e5 + 5; const int inf = 1e9; const int mod = 10000019; int a[maxn]; long long qwr(long long x,long long y){ long long res = 1; x = x % mod; while(y != 0){ if(y & 1)res = (res * x) % mod; x = (x*x) % mod; y = (y >> 1); } return res; } int main(){ int n; long long ans = 0; scanf("%d",&n); for(int i = 1; i <= n ; i++){ scanf("%d",&a[i]); } for(int i = 1 ; i <= n ; i++){ ans = (ans + qwr(a[i],i)) % mod; } printf("%lld ",ans); } 然后我根据自己的理解写整理了一下快速幂的模板 int mod(int a, int b, int c){ Int ans = 1; a = a % c; while(b > 0){ if(b % 2 == 1); ans = (ans * a) % c; b = b / 2; a = (a * a) % c; } return ans; }