解题思路:
等差数列公式: an=a1+(n-1)d
等比数列公式:an=a1*q(n-1)
等比数列中的项数k能取到109得到的结果非常大,所以快速幂方法可以解决数据益出
快速幂
①如果b是奇数,ab=a*a(b-1)
②如果b是偶数,ab=a(b/2)*a(b/2)
举个例子210
210 | 幂为10偶数 | 先取25 | 210=25*25 |
25 | 幂为5奇数 | 先取24 | 25=2*24 |
24 | 幂为4偶数 | 先取22 | 24=22*22 |
22 | 幂为2偶数 | 先取21 | 22=21*21 |
21 | 幂为1奇数 | 先取20 | 21=2*20 |
20=1然后从下向上回退计算,递归出口 |
注意事项:注意每一步结果都要取模,定义long long类型
参考代码:
#include<bits/stdc++.h> using namespace std; typedef long long LL; int quick(LL a,LL b,LL m) { if(b==0) return 1;//如果b为0,那么a^0=1 else if(b%2==1)//b为奇数,转换为b-1 return a*quick(a,b-1,m)%m; else if(b%2==0)//b为偶数,转换为b/2 { LL t=quick(a,b/2,m)%m; return t*t%m; } } int main() { int n; LL a,b,c,d; scanf("%d",&n); while(n--) { scanf("%lld%lld%lld%lld",&a,&b,&c,&d); if(a==b&&b==c) { printf("%lld\n",a%200907); } else if(b-a==c-b) { printf("%lld\n",a+((d-1)%200907*(b-a)%200907)%200907); } else if(b/a==c/b) { printf("%lld\n",quick((b/a),d-1,200907)*a%200907); } } }
0.0分
2 人评分
【绝对值排序】 (C++代码)浏览:670 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:517 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:1090 |
三角形 (C++代码)递归(存在大量重复计算,容易出现时间超限)浏览:774 |
1124题解浏览:591 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:696 |
杨辉三角 (C语言代码)浏览:676 |
母牛的故事 (C语言代码)浏览:451 |
C语言训练-斐波纳契数列 (C语言代码)浏览:503 |
众数问题 (C语言代码)浏览:621 |