Fibonacci, un celebru matematician italian din Evul Mediu, a descoperit un șir de numere naturale cu multiple aplicații, șir ce-i poartă numele:
Fibonacci(n)={1dacă n=1 sau n=2 Fibonacci(n−1)+Fibonacci(n−2)dacă n>2
Fascinat de șirul lui Fibonacci, și mai ales aplicațiile acestui șir în natură, Iccanobif, un matematician în devenire, a creat un șir si el un care-i poartă numele:
Iccanobif(n)={1dacă n=1 sau n=2 răsturnat(Iccanobif(n−1))+răsturnat(Iccanobif(n−2))dacă n>2
Obținându-se astfel șirurile:
- Fibonacci:
1,1,2,3,5,8,13,21,34,55,89,144, … - Iccanobif:
1,1,2,3,5,8,13,39,124,514,836, …
Iccanobif, se întreabă acum, ce număr are mai mulți divizori numere naturale: al n-lea termen din șirul Fibonacci sau al n-lea termen din șirul său.
Cerințe
Scrieți un program care să citească un număr natural n și să afișeze:
a) al n-lea termen din șirul lui Fibonacci și numărul său de divizori
Obținându-se astfel șirurile:
- Fibonacci:
1,1,2,3,5,8,13,21,34,55,89,144, … - Iccanobif:
1,1,2,3,5,8,13,39,124,514,836, …
Iccanobif, se întreabă acum, ce număr are mai mulți divizori numere naturale: al n-lea termen din șirul Fibonacci sau al n-lea termen din șirul său.
Cerințe
Scrieți un program care să citească un număr natural n și să afișeze:
a) al n-lea termen din șirul lui Fibonacci și numărul său de divizori
b) al n-lea termen din șirul lui Iccanobif și numărul său de divizori
Date de intrare
Fișierul de intrare siruri2.in conține pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe linia a doua a fișierului se găsește un număr natural n.
Date de ieșire
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerințe. În acest caz, în fișierul de ieșire siruri2.out se vor scrie al n-lea termen din șirul lui Fibonacci și numărul său de divizori.
Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerințe. În acest caz, în fișierul de ieșire siruri2.out se vor scrie al n-lea termen din șirul lui Iccanobif și numărul său de divizori
Restricții și precizări
1 ≤ n ≤ 50- Pentru rezolvarea corectă a primei cerinţe se acordă 50% din punctaj, iar pentru cerința a doua se acordă 50% din punctaj.
Exemplul 1
siruri2.in
1 8
siruri2.out
21 4
Exemplul 2
siruri2.in
2 9
siruri2.out
124 6
Explicații
Pentru primul exemplu: Al optulea termen din șirul lui Fibonacci este 21, iar 21 are 4 divizori. (p fiind 1 se rezolvă doar cerința a)
Pentru al doilea exemplu: Al nouălea termen din șirul lui Iccanobif este 124, iar 124 are 6 divizori. (p fiind 2 se rezolvă doar cerința b)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("siruri2.in");
ofstream fout("siruri2.out");
unsigned long long fib(unsigned long long n)
{
long long f1=1,f2=1,f3;
if(n==1) return 1;
else if(n==2) return 1;
else
{
while(n>2)
{
f3=f1+f2;
f1=f2;
f2=f3;
n--;
}
return f3;
}
}
unsigned long long ogl(unsigned long long n)
{
long long ogl=0;
while(n!=0)
{
ogl=ogl*10+n%10;
n=n/10;
}
return ogl;
}
unsigned long long ico(unsigned long long n)
{
unsigned long long f1=1,f2=1,f3;
if(n==1) return 1;
else if(n==2) return 1;
else
{
while(n>2)
{
f3=ogl(f1)+ogl(f2);
f1=f2;
f2=f3;
n--;
}
return f3;
}
}
unsigned long long nrdiv(unsigned long long n)
{
long long cnt=0;
for(unsigned long long i=1;i*i<=n;i++)
{
if(n%i==0) cnt += 2;
if(i*i==n) cnt--;
}
return cnt;
}
int main()
{
int n,p;
fin>>p>>n;
if(p==1)
fout<<1ull*fib(n)<<" "<<nrdiv(fib(n));
else fout<<1ull*ico(n)<<" "<<nrdiv(ico(n));
return 0;
}
