首页 > 代码库 > 杭电 2817 A sequence of numbers【快速幂取模】
杭电 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); } }}
杭电 2817 A sequence of numbers【快速幂取模】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。