Pagini recente » Cod sursa (job #119720) | Cod sursa (job #1429792) | Cod sursa (job #846144) | Cod sursa (job #1788273) | Cod sursa (job #3246098)
#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;
}