Pagini recente » Cod sursa (job #487108) | Cod sursa (job #2057899) | Cod sursa (job #3220522) | Cod sursa (job #2306316) | Cod sursa (job #3276718)
#include <fstream>
#include <bitset>
using namespace std;
const int NMAX = 5001;
ifstream fin("mins.in");
ofstream fout("mins.out");
int c, d;
long long sol;
short v[NMAX]; ///v[i] => Produsul a cator numere prime distincte mai mici decat i este egal cu i (asemanator pb pinex pe infoarena)
void solutie(int i)
{
long long a = 0, b = 0;
if(!v[i]) /// i este prim
{
for(int j = i; j <= d; j += i)
{
++v[j];
if(j <= c) ++a; ///Merg (i, j) si (j, i)
else ++b; ///Merge doar (i, j)
}
sol += a * (a + b);
}
else if (v[i] != 1) /// i nu este divizibil cu patratul unui nr prim
{
for(int j = i; j <= d; j += i)
{
--v[j];
if(j <= c) ++a; /// Merg (i, j) si (j, i)
else ++b; /// Merge doar (i, j)
}
sol -= a * (a + b);
}
}
int main()
{
fin >> c >> d;
--c, --d;
if(c > d) swap(c, d);
for(int i = 2; i <= c; ++i) solutie(i);
fout << (long long)c*d - sol;
return 0;
}