hdu 2817 A sequence of numbers （快速求冪）

這道題第一次小競賽的時候俺連題目都沒讀懂，後來聽老師講了，明白了題意，可是還不會！囧！！！

#￥#￥#%￥￥%%￥%￥%……￥%￥%……&……&*&*（（）&*（%……&%￥￥%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

為什麼呢！因為那時俺還不會快速求冪，對，就是快速求冪，這道題的價值也就是教我學會了這點！

&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

題意：給你一個序列的前三個數，這個序列不是等差序列就是等比序列，給你一個n，求序列的第n項（呵呵，簡單吧！）

***************************************************************************************************************************************************

#include<stdio.h>

#define N 200907


__int64 pow(__int64 q,__int64 n)
{
__int64 ans=1;
while(n)
{
if(n&1)
ans=ans%N*(q%N)%N;
n/=2;
q=q%N*(q%N)%N;
}
return ans;
}


int main()
{
__int64 t,a,b,c,q,d,n,ans;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&n);
if(2*b==a+c)
{
d=b-a;
ans=(a+(n-1)*d%N)%N;
}
else
{
q=b/a;
ans=a*pow(q,n-1)%N;
}
printf("%I64d\n",ans);
}
return 0;
}