Pagini recente » Cod sursa (job #3333400) | Cod sursa (job #2236079) | Diferente pentru problema/cbinteractiv intre reviziile 28 si 19 | Cod sursa (job #3339632) | Cod sursa (job #3311291)
#include <iostream>
#include <fstream>
using namespace std;
const int Cmax = 1000005;
int c, d, ciur[Cmax];
long long antiSol;
bool bad[Cmax];
int main()
{
ifstream fin("mins.in");
ofstream fout("mins.out");
fin >> c >> d;
c--;
d--;
int n = min(c,d);
// cautam perechile (x,y) cu 1 <= x <= c && 1 <= y <= d
// astfel incat cmmdc(x, y) >= 2
for (int i = 2; i <= n; i++)
{
if (ciur[i] == 0)
{
for (int j = i; j <= n; j += i)
{
ciur[j]++;
}
long long k = 1LL * i * i;
for(long long j = k; j <= n; j += k){
bad[j] = 1;
}
}
}
for (int k = 2; k <= n; k++)
{
if(!bad[k]){
long long aux = 1LL * (c / k) * (d / k);
if (ciur[k] % 2 == 1)
{
antiSol += aux;
}
else
{
antiSol -= aux;
}
}
}
fout << 1LL * c*d - antiSol;
return 0;
}