解题思路:
等差数列公式: 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语言代码)浏览:553 |
简单的a+b (C语言代码)浏览:524 |
【偶数求和】 (C语言代码)浏览:639 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:694 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:470 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:713 |
1025题 初学者,求帮忙看下,不知道哪错了浏览:316 |
核桃的数量 (C语言代码)浏览:825 |
简单的a+b (C语言代码)浏览:655 |
P1001 (Java代码)浏览:687 |