对 $m$ 取模啊!
by SegTree @ 2022-06-19 12:30:56
否则一定爆 `long long`
by SegTree @ 2022-06-19 12:31:23
@[longyue3ye](/user/723517)
by SegTree @ 2022-06-19 12:31:41
@[jpb_Saturn](/user/678965) 什么意思
by Joseph__Joestar @ 2022-06-20 11:59:34
```cpp
long long a=0,b=1,t;
do{
t=b;
b=a+b;
a=t;
++cnt;
}while(a%m!=0||b%m!=1);
```
这个过程中 $a$,$b$,$t$ 都没有对 $m$ 取模。
然而,计算斐波那契第 $m$ 项斐波那契数列增长会特别快,在 $N\ge 50$ 好像就会导致 $fib_n$ 爆 `long long`,造成数据溢出,导致一直跳不出循环或者计算出错。所以应该改为:
```cpp
long long a=0,b=1,t;
do{
t=b%m;
b=(a+b)%m;
a=t%m;
++cnt;
}while(a%m!=0||b%m!=1);
```
by SegTree @ 2022-06-20 12:08:59
@[longyue3ye](/user/723517)
by SegTree @ 2022-06-20 12:09:15
@[jpb_Saturn](/user/678965)
为什么abt要对m取模,这样不会影响结果吗
by Joseph__Joestar @ 2022-06-20 23:05:32
因为你的计算都是模 $m$ 意义下的,同时可以改为 `while(a!=0||b!=1)`。
by SegTree @ 2022-06-21 07:47:38
@[longyue3ye](/user/723517)
by SegTree @ 2022-06-21 07:47:52
@[jpb_Saturn](/user/678965)
谢谢你,我懂了
by Joseph__Joestar @ 2022-06-21 10:28:17