c++ - acm小题之关于大整数对1000000007取模
ringa_lee
ringa_lee 2017-04-17 13:31:03
0
4
1129

#include <stdio.h>
#include <math.h>
int main ()
{int a,i=1,n,T;
scanf("%d",&T);
n=T;
int q[T+1]; 
while(T--)
{scanf("%d",&a);
q[i++]=(long)((1/sqrt(5))*((pow(((1+sqrt(5))/2),a+2)-pow(((1-sqrt(5))/2),a+2))-1))%1000000007;
 
 }
for(i=1;i<=n;i++) 
 printf("%d\n",q[i]);}

运行结果:

此题我算出Sn了,可是在取模这里一直有问题。。。求解计算过程中怎么防止溢出

ringa_lee
ringa_lee

ringa_lee

全部回复(4)
伊谢尔伦

每做一次加法和乘法,就取一次模

大家讲道理

用递推算,不要用通项公式。

m = 1000000007
S(n)=(F(1)+F(2)+...+F(n)) % m
    =(F(1)%m + F(2)%m + ... + F(n)%m) % m

F(n) = F(n-2) + F(n-1)
F(n)%m = (F(n-2) + F(n-1)) % m
       = (F(n-2)%m + F(n-1)%m) % m
迷茫

感谢两位大神啦ლ(╹ε╹ლ) 算出来了

阿神

(a+b)%c==(a%c)+(b%c)
乘法同理

经评论指正应是:(a+b)%c==((a%c)+(b%c))%c

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!