Pagini recente » Cod sursa (job #800517) | Cod sursa (job #655381)
Cod sursa(job #655381)
#include <fstream>
#include <queue>
using namespace std;
typedef long long int64;
int64 N, K;
int D[24];
int64 result;
int64 Comb[24][24], C[24][24];
char nrb[1 << 22], log[1 << 22];
int64 val[1 << 21];
inline int64 cmmdc(int64 a, int64 b)
{
if (b == 0) return a;
return cmmdc(b, a % b);
}
int main()
{
ifstream fin("light2.in");
ofstream fout("light2.out");
for (int i = 1; i < (1 << 22); ++i)
{
nrb[i] = nrb[i & (i - 1)] + 1;
if (i >= 2) log[i] = log[i >> 1] + 1;
}
Comb[0][0] = 1;
for (int i = 1; i <= 22; ++i)
{
Comb[i][0] = 1;
for (int j = 1; j <= i; ++j)
{
Comb[i][j] = Comb[i - 1][j] + Comb[i - 1][j - 1];
C[i][j] = C[i][j - 1] + Comb[i][j] * (-C[j][j - 1] + j % 2);
}
}
fin >> N >> K;
for (int i = 1; i <= K; ++i)
fin >> D[i];
val[0] = 1;
int64 value;
for (int i = 1; i < (1 << K); ++i)
{
int last = i;
while ((last & (last - 1)) != 0)
last &= last - 1;
value = val[i ^ last];
last = log[last];
if (value == -1)
{
if (i < (1 << 21))
val[i] = value;
continue;
}
value = value / cmmdc(value, D[last + 1]) * D[last + 1];
if (value > N)
value = -1;
if (value == -1)
{
if (i < (1 << 21))
val[i] = value;
continue;
}
if (i < (1 << 21))
val[i] = value;
result += (-C[nrb[i]][nrb[i] - 1] + nrb[i] % 2) * (N / value);
}
fout << result;
fin.close();
fout.close();
}