Ֆիբոնաչիի n-երորդ անդամի հաշվարկը (m-ի վրա բաժանելիս ստացվող մնացորդով)
Ֆիբոնաչիի հաջորդականությունը սահմանվում է այնպես, որ յուրաքանչյուր նոր անդամ ստանում ենք նախորդ երկու անդամների գումարից, ընդ որում առաջին երկու անդամները 0 և 1 են.
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
n թիվը, կհաշվարկի n-րդ Ֆիբոնաչիի անդամի m-ի վրա բաժանելիս ստացվող մնացորդը:Քանի որ մեզ հետաքրքրում է միայն արդյունքի
m-ի վրա բաժանելիս ստացվող մնացորդը, n-ը կարող է լինել շատ մեծ դրական թիվ:Մուտք
Մուտքի միակ տողում տրված են երկու ամբողջ թվեր
n (0 ≤ n ≤ ) և m (1 ≤ m ≤ 50):Ելք
Ծրագիրը պետք է տպի -ի արժեքը:
Օրինակներ
Մուտք | Ելք |
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Պարզաբանում
- fib(0) = 0 ⇒ 0 mod 5 = 0
- fib(1) = 1 ⇒ 1 mod 5 = 1
- fib(6) = 8 ⇒ 8 mod 5 = 3
Հուշում 1
Քանի որ Ֆիբոնաչիի անդամները հաշվում ենք ըստ
m-ի վրա բաժանելիս ստացվող մնացորդով, ինչպես նաև յուրաքանչյուր հաջորդ թիվ կախված է միայն նախորդ երկու թվերից, որոշակի պահի հաջորդականությունը սկսում է կրկնվել: Կարող եք փորձել տպել բազմաթիվ արժեքներ m-ի վրա բաժանելուս ստացվող մնացորդով և տեսնել այն շղթան, որից հետո թվերը կրկնվում են:Հուշում 2
Քանի որ թվերը սկսում են կրկնվել որոշակի պահից, կարելի է հաշվել
n-րդ Ֆիբոնաչիի անդամը, առանց բոլոր արժեքները հաշվելու:Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB