杭电 2817 A sequence of numbers【快速幂取模】

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2817

解题思路:arithmetic or geometric sequences 是等差数列和等比数列的意思,

即令输入的第一个数为a(1),那么对于等差数列 a(k)=a(1)+(k-1)*d,即只需要求出 a(k)%mod   又因为考虑到k和a的范围,

所以对上式通过同余作一个变形:即求出 (a(1)%mod+(k-1)%mod*(d%mod))%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\n",((k-1)%mod*(b-a)%mod+a%mod)%mod); else
{
__int64 q=b/a;
printf("%I64d\n",(quick_mod(q,k-1)*(a%mod))%mod);
} }
}
上一篇:菊花加载第三方--MBprogressHUD


下一篇:Android6的Logger日志系统