快速幂的递归方法

解题思路:

等差数列公式: an=a1+(n-1)d

等比数列公式：an=a1*q^(n-1)

等比数列中的项数k能取到10⁹得到的结果非常大，所以快速幂方法可以解决数据益出

快速幂

①如果b是奇数，a^b=a*a^(b-1)

②如果b是偶数，a^b=a^(b/2)*a^(b/2)

举个例子2¹⁰

注意事项:注意每一步结果都要取模，定义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);
		}
		
	}
}