Cod sursa(job #640174)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 24 noiembrie 2011 21:08:29
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
#include<cmath>
using namespace std;

long long p,pr;
int x,y,m,mi,a[1000000];
short int t[1000000];

void gen();
void back(int);

int main()
{
    ifstream f("mins.in");
    ofstream g("mins.out");
    f >> x >> y;
	x--;y--;
    if (x<y) mi=x; else mi=y;
    m=0;
    p=x*y;
    gen();
    pr=1;
    back(1);
    g << p;
    return 0;
}

void gen()
{
    int i,j;
	for (i=2;i<=mi;i++)
    if (t[i]==0)
    {
        a[++m]=i;
        for (j=i*i;j<=mi;j+=i)
        a[j]=1;
    }
}

void back(int k)
{
    int i;
    for(i=1;i<=m;i++)
    {
        pr*=a[i];
        if (pr<=mi)
        {
            if (k%2==0) p+=(x/pr)*(y/pr); else p-=(x/pr)*(y/pr);
            back(k+1);
        }
        pr/=i;
    }
}