Cod sursa(job #2161888)

Utilizator Daria09Florea Daria Daria09 Data 11 martie 2018 21:46:15
Problema Indep Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <math.h>
#define NMAX 505
using namespace std;
ifstream f("indep.in");
ofstream g("indep.out");
int p2[NMAX][NMAX],ans[NMAX],prim[NMAX*2],rez[NMAX],n,a[NMAX],MAX,nr,v[NMAX],ciur[NMAX*2];
void read()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>a[i],MAX=max(MAX,a[i]);
    f.close();
}
int verif(int x)
{
    int sol=0,i=0;
    while(x!=1)
    {
        int w=0;
        ++i;
        while(x%prim[i]==0)
        {
            w++;
            x/=prim[i];
        }
        if(w>1)
            return 0;
        if(w!=0)
            sol++;
    }
    return sol;
}
void produs(int a[],int z,int b[])
{
    int t=0,i;
    for(i=1; i<=a[0]||t; i++,t/=10)
        b[i]=(t+=a[i]*z)%10;
    b[0]=i-1;
}
int divv(int x)
{
    int sol=0;
    for(int i=1; i<=n; i++)
        if(a[i]%x==0)
            sol++;
    return sol;
}
void adunare(int a[],int b[])
{
    int t=0,i;
    for(i=1; i<=a[0]||i<=b[0]||t; i++,t/=10)
        a[i]=(t+=a[i]+b[i])%10;
    a[0]=i-1;
}
void scadere(int a[],int b[])
{
    int t=0;
    for(int i=1; i<=a[0]; i++)
    {
        a[i]=a[i]-b[i]-t;
        if(a[i]>=0)
            t=0;
        else
        {
            a[i]+=10;
            t=1;
        }
    }
    while(a[0]>1&&a[a[0]]==0)
        a[0]--;
}
void prelucrare()
{
    p2[0][0]=p2[0][1]=1;
    for(int i=1; i<=n; i++)
        produs(p2[i-1],2,p2[i]);
    v[0]=v[1]=1;
    for(int i=0;i<=n;i++)
        scadere(p2[i],v);
    prim[1]=2; nr=1;
    for(int i=4; i<=MAX; i+=2) ciur[i]=1;
    for(int i=3; i<=MAX; i+=2)
        if(ciur[i]==0)
        {
            prim[++nr]=i;
            for(int j=2*i; j<=MAX; j+=i) ciur[j]=1;
        }
}
void solve()
{
    int x=n;
    for(int i=2; i<=MAX; i++)
    {
        int ok=verif(i);
        if(ok==0)continue;
        int s=divv(i);
        if(s!=0)
        {
            if(ok%2==1)
                adunare(ans,p2[s]);
            else
                scadere(ans,p2[s]);
        }
    }
    adunare(rez,p2[n]);
    scadere(rez,ans);
}
void write()
{
    for(int i=ans[0]; i>=1; i--)
        g<<rez[i];
    g.close();
}
int main()
{
    read();
    prelucrare();
    solve();
    write();
    return 0;
}