解题思路:
等差数列公式: 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语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:584 |
最长单词 (C语言代码)浏览:1376 |
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1315 |
字符串比较 (C语言代码)答案错误????浏览:597 |
A+B for Input-Output Practice (V) (C语言代码)浏览:623 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:2080 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:594 |
【计算球体积】 (C语言代码)浏览:1102 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:2092 |
文科生的悲哀 (C语言代码)浏览:1401 |