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

Question

#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了，可是在取模这里一直有问题。。。求解计算过程中怎么防止溢出

Answer 1

For each addition or multiplication, take the modulus

Answer 2

Use recursive calculations instead of general formulas.

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

Answer 3

Thank you to the two great gods ლ(╹ε╹ლ) for figuring it out

Answer 4

(a+b)%c==(a%c)+(b%c)
Same as multiplication

After comments, the correction should be: (a+b)%c==((a%c)+(b%c))%c