Ֆիբոնաչիի 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