Cod sursa(job #3246098)

Utilizator 0021592Grecu rares 0021592 Data 1 octombrie 2024 20:44:41
Problema Mins Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#define int long long
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
int mask, j, k, i, n, m, s, lg, v[20], best;
int v1[] = {-1, 1};
void fact(int x);
int32_t main()
{
    in >> n >> m;
    if (n > m)
        swap(n, m);
    n--; m--;
    for (i = 1; i <= n; i++)
    {
        s=0;
        lg=0;
        fact(i);
        for (mask = 1; mask < (1<<lg); mask++)
        {
            int nr = 0, p = 1;
            for (j = 1; j <= lg; j++)
                if ((mask&(1<<(j-1))))
                {
                    nr++;
                    p*=v[j];
                }
            s += m/p*v1[nr%2];
        }
        best += m-s;
    }
    out << best;
    return 0;
}
void fact(int x)
{
    int i = 2;
    bool ok = 0;
    while(x%i == 0)
    {
        x/=i;
        ok=1;
    }
    if (ok == 1)
        v[++lg] = i;
    for (i = 3; i * i <= x; i+=2)
    {
        ok = 0;
        while(x%i == 0)
        {
            x/=i;
            ok=1;
        }
        if (ok == 1)
            v[++lg] = i;
    }
    if(x!=1)
        v[++lg] = x;
}