c++ - acm小题之关于大整数对1000000007取模

问题描述

#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('%dn',q[i]);}

运行结果：

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

问题解答

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

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

m = 1000000007S(n)=(F(1)+F(2)+...+F(n)) % m =(F(1)%m + F(2)%m + ... + F(n)%m) % mF(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回答3：

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

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

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