Pagini recente » Cod sursa (job #3315344) | Cod sursa (job #2236082) | Cod sursa (job #3322889) | Diferente pentru problema/cbinteractiv intre reviziile 17 si 18 | Cod sursa (job #3311286)
#include <fstream>
using namespace std;
const int Cmax = 1000005;
int c, d, ciur[Cmax], sol;
bool bad[Cmax];
int main()
{
ifstream fin("mins.in");
ofstream fout("mins.out");
fin >> c >> d;
c--;
d--;
// cautam perechile (x,y) cu 1 <= x <= c && 1 <= y <= d
// astfel incat cmmdc(x, y) >= 2
for (int i = 2; i <= min(c, d); i++)
{
if (ciur[i] == 0)
{
for (int j = i; j <= min(c, d); j += i)
{
ciur[j]++;
}
for (int j = i * i; j <= min(c, d); j += i * i)
{
bad[j] = true;
}
}
}
for (int k = 2; k <= min(c, d); k++)
{
if (bad[k])
{
continue;
}
if (ciur[k] % 2 == 1)
{
sol -= (c / k) * (d / k);
}
else
{
sol += (c / k) * (d / k);
}
}
fout << sol + (c * d);
return 0;
}