Pagini recente » Cod sursa (job #518061) | Cod sursa (job #1213477) | Cod sursa (job #2414661) | Cod sursa (job #2240950) | Cod sursa (job #474124)
Cod sursa(job #474124)
#include <fstream>
using namespace std;
ifstream fin("mins.in");
ofstream fout("mins.out");
void PreGen();
void Read();
void Solve();
long long NumP(int x);
void Fact(int x);
void Write();
int n, m, sp, sf;
int prim[100], fac[20];
bool pr[1000];
long long wrong;
int main()
{
PreGen();
Read();
Solve();
Write();
}
void PreGen()
{
prim[++sp] = 2;
for (int i = 3; i <= 1000; i += 2)
if (pr[i] == false)
{
prim[++sp] = i;
for (int j = i * i; j <= 1000; j += 2 * i)
pr[j] = true;
}
}
void Read()
{
fin >> n >> m;
}
void Solve()
{
for (int i = 1; i < n; ++i)
wrong += NumP(i);
}
long long NumP(int x)
{
sf = 0;
Fact(x);
int prod, what;
long long result = 0;
for (int i = 1; i < (1 << sf); ++i)
{
prod = 1;
for (int j = 0; j < sf; ++j)
if (((1 << j) & i) != 0)
prod *= fac[j + 1];
what = (m - 1) / prod;
int np = 0, aux = i;
while (aux)
{
++np;
aux &= aux - 1;
}
if (np % 2 == 1) result += what;
else result -= what;
}
return result;
}
void Fact(int x)
{
for (int i = 1; i <= sp; ++i)
if (x % prim[i] == 0)
{
fac[++sf] = prim[i];
while (x % prim[i] == 0)
x /= prim[i];
}
if (x != 1)
fac[++sf] = x;
}
void Write()
{
fout << (n - 1) * (m - 1) - wrong;
}