Cod sursa(job #1750468)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 30 august 2016 12:25:24
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("mins.in");
ofstream g("mins.out");
const int MAXP=1002;
int m,n,prim[1001],lp=0,lg,t,p[1001],sol,card;
bool b[1005];
void generareNumerePrime()
{
    int i,j;
    for(i=4; i<MAXP; i+=2)
        b[i]=1;
    for(i=3; i*i<MAXP; i+=2)
        if(b[i] == 0)
            for(j = i * i; j < MAXP; j += i)
                b[j] = 1;
    for(i = 2; i < MAXP; i++)
        if(b[i] == 0) prim[++lp] = i;
}
void generareDivizori(int a)
{
    lg=0;
    for(int j=1; prim[j]*prim[j]<=a; j++)
        if(a%prim[j]==0)
        {
            p[++lg]=prim[j];
            while(a%prim[j]==0) a/=prim[j];
        }
    if(a>1) p[++lg]=a;
}
int main()
{
    generareNumerePrime();
    f>>m>>n;
    m--;
    n--;
    int minim=min(m,n),maxim=max(m,n);
    for(int a=2; a<=minim; a++)
    {
        generareDivizori(a);
        int nt=1<<lg;
        card=0;
        for(int i=1; i<nt; i++)
        {
            long long int prod=1;
            int j=0,p2,ndiv=0;
            while((p2=1<<j)<=i)
            {
                if(p2&i)
                {
                    prod*=p[j+1];
                    ndiv++;
                }
                j++;
            }
            long long int t=a/prod;
            if(ndiv%2==0)
                card-=t;
            else
                card+=t;
        }
    }
    card=card*2-1;
    sol=m*n;
    sol-=card;
    for(int a=minim+1; a<=maxim; a++)
    {
        generareDivizori(a);
        int nt=1<<lg;
        card=0;
        for(int i=1; i<nt; i++)
        {
            long long int prod=1;
            int j=0,p2,ndiv=0;
            while((p2=1<<j)<=i)
            {
                if(p2&i)
                {
                    prod*=p[j+1];
                    ndiv++;
                }
                j++;
            }
            long long int t=minim/prod;
            if(ndiv%2==0)
                card-=t;
            else
                card+=t;
        }
    }
    sol-=card;
    g<<sol;
    return 0;
}