Cod sursa(job #1850653)

Utilizator FeriCsiki Francisc Alexandru Feri Data 18 ianuarie 2017 20:15:49
Problema Indep Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>


using namespace std;

ifstream in("indep.in");
ofstream out("indep.out");

int v[501],nr[501][501]; //nr[i][j]=numarul de multimi cu i el si cmmdc j
//nr[i]=sum(nr[i])

int minim(int a, int b)
{
    if(a<b)  return a;
    return b;
}

int cmmdc(int a,int b)
{
    int i=2,k=minim(a,b);
    while(i*i<=k && (a%i!=0 || b%i!=0))
    {
        i++;
    }
    if(i<k)
        return i;
    if(i*i==k && a%i==0 && b%i==0)
        return k;
    return 1;

}

int main()
{
    int i,j,n,k,div=1;
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>v[i];
        if(v[i]>k)
            k=v[i];
    }
    nr[1][v[1]]=1;
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=k;j++)
        {
            nr[i][j]=nr[i-1][j];
        }
        for(j=1;j<=k;j++)
        {
            div=cmmdc(j,v[i]);
            nr[i][div]+=nr[i-1][j];
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            out<<nr[i][j]<<" ";
        }
        out<<'\n';
    }
    out<<nr[n][1];
    return 0;
}