Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T.

Cerința

Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1], A[2],...,A[N].

Date de intrare

Fișierul de intrare fibodiv.in conţine pe prima linie numerele N și T separate printr-un spațiu, iar pe a doua linie N numere naturale, A[1], A[2],...,A[N], separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire fibodiv.out va conţine pe prima linie numărul natural D,cu semnificația de mai sus.

Restricții și precizări

1 ≤ N ≤ 15
2 ≤ T ≤ 10¹⁸
2 ≤ A[i] ≤ 50, 1 ≤ i ≤ N

Exemplu

fibodiv.in

3 20
3 6 10

fibodiv.out

Explicație

N = 3; T = 20; A1 = 3, A2 = 6, A3 = 10. Primii 20 de termeni ai șirului Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765. Printre aceștia se găsesc 6 termeni divizibili cu cel puțin unul dintre numerele 3, 6, 10 și anume: 3, 21, 144, 610, 987, 6765.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema fibodiv:

// prof. Ciprian Chesca - Fibonacci + PINEX cu generare submultimi
// 100 puncte


#include <fstream>

#define nmax 101
#define ll long long

using namespace std;

ifstream f("fibodiv.in");
ofstream g("fibodiv.out");

ll n,t;
ll per[nmax],a[nmax],st[nmax];
ll sol=0;

// calculez perioada restransa a aparitiei unui termen divizibil cu a[1]..a[n] in sirul Fibonacci
void perioada(ll n)
{
ll x,y,z,p,i;
bool ok;

for(i=1;i<=n;i++)
{
    x=1;y=1;ok=false;p=2;
    while (!ok)
        {
        z=(x+y)%a[i];
        x = y;
        y = z;
        p++;
        if (z==0) {per[i]=p;ok=true;}
        }
}}


ll cmmdc(ll a, ll b)
{
    ll d=a,i=b,r=d%i;
    while (r)
    {
        d=i;
        i=r;
        r=d%i;
    }
    return i;
}


ll n_cmmmc(ll x[], ll n)
{
    ll i,w = x[1];
    for(i=2;i<=n;i++)
        w=(w*x[i])/cmmdc(w,x[i]);

    return w;
}


void inout(ll k)
{
ll p = n_cmmmc(st,k);
if (k%2==0) sol-=t/p;
    else    sol+=t/p;
}


void parti()
{
    ll i,j,k,l = 1 << n; // l = 2^n
    for(i=1;i<l;i++)
    {

        k=0;
        for(j=0;j<n;j++)
            if ((i>>j) & 1)
                st[++k]=per[j+1];
        inout(k);


    }
}


int main()
{
ll i;

f>>n>>t;
for(i=1;i<=n;i++)
    f >> a[i];


perioada(n);

parti();

g<<sol<<"\n";


f.close();
g.close();
return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2053 fibodiv

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2053 fibodiv de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2053 fibodiv