杭電2817 A sequence of numbers【高速べき乗取型】
1139 ワード
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2817
問題解決の考え方:アリスト・ゲーム・エム・セックsequencesは等差数列と等比数列を意味し、
命令入力の最初の個数はa(1)であり、等差数列a(k)=a(1)+(k-1)*dに対しては、a(k)%modのみを求める必要があります. またkとaの範囲を考慮して、
上式に対しては、同余を通じて変形します.すなわち、(a(1)%mod+(k-1)%mod*(d%mod)を求めます.
等比数列a(k)=a(1)*q^k-1;すなわち、求められているa(k)%mod同理は、同残変形により(((a(1)%mod)*(q^k-1)%mod))%modとなり、これにより、高速べき乗取型が可能となる.
反省:最初はa(k)の通項式を変形してから取り残していませんでした.タイムアウトになりました.
問題解決の考え方:アリスト・ゲーム・エム・セックsequencesは等差数列と等比数列を意味し、
命令入力の最初の個数はa(1)であり、等差数列a(k)=a(1)+(k-1)*dに対しては、a(k)%modのみを求める必要があります. またkとaの範囲を考慮して、
上式に対しては、同余を通じて変形します.すなわち、(a(1)%mod+(k-1)%mod*(d%mod)を求めます.
等比数列a(k)=a(1)*q^k-1;すなわち、求められているa(k)%mod同理は、同残変形により(((a(1)%mod)*(q^k-1)%mod))%modとなり、これにより、高速べき乗取型が可能となる.
反省:最初はa(k)の通項式を変形してから取り残していませんでした.タイムアウトになりました.
#include<stdio.h>
#define mod 200907
__int64 quick_mod( __int64 a,__int64 b)
{
__int64 ans=1;
while(b)
{
if(b&1)
{
ans=ans*a%mod;
}
b>>=1;
a=a*a%mod;
}
return ans;
}
int main()
{
int ncase;
__int64 a,b,c,k;
scanf("%d",&ncase);
while(ncase--)
{
scanf("%I64d %I64d %I64d %I64d",&a,&b,&c,&k);
if(b-a==c-b)
printf("%I64d
",((k-1)%mod*(b-a)%mod+a%mod)%mod);
else
{
__int64 q=b/a;
printf("%I64d
",(quick_mod(q,k-1)*(a%mod))%mod);
}
}
}