Решения задач acmp.ru
Главная
Вход
Регистрация
Воскресенье, 20.09.2020, 20:57Приветствую Вас Гость | RSS
Меню сайта

Категории раздела
Pascal [121]
C++ [76]

Поиск

Мини-чат
200

Легкий заработок!

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

Форма входа

Главная » Файлы » C++

0337 Лампочки

Скачать файл можно после просмотра рекламы:

05.06.2012, 03:07
const int maxP = 50;

#include <stdio.h>
#include <map>
#include <vector>

int gcd(int r1, int r2)
{
for (int r3;r2 != 0;)
{
r3 = r1 % r2;
r1 = r2;
r2 = r3;
}
return r1;
}


__int64 lcm(int a, int b) {
return (a / gcd(a, b) ) * (__int64)b;
}


typedef std::map<int,  int> MTable;

void merge(MTable &dst, int v, int s)
{
MTable::iterator i = dst.find(v);
if (i == dst.end() )
dst[v] = s;
else
{
int n = i->second + s;
if (n != 0)
i->second = n;
else
dst.erase(i);
}
}


int main(int argc, char ** argv)
{
FILE *in, *out;
in  = fopen("input.txt", "r");
out = fopen("output.txt", "w");
MTable  l;
int n, k;
int maxss = 0;
fscanf(in, "%d%d", &n, &k);
std::vector<bool> kk(maxP);
for (int i = 0; i < k; i++)
{
int p;
fscanf(in, "%d", &p);
kk[p-1] = !kk[p-1];
}

for (int i = 0; i < maxP; i++)
if (kk[i])
{
int p = i + 1;
MTable r(l);
for (MTable::const_iterator i = l.begin(); i != l.end(); ++i)
{
__int64 v = lcm(i->first, p);
if (v <= n)
merge(r, (int)v, -2 * i->second);
}
l.swap(r);
merge(l, p, 1);
}

__int64 result = 0;

for (MTable::const_iterator i = l.begin(); i != l.end(); ++i)
result += (n / i->first) * i->second;

fprintf(out, "%ld\n", (int)result);

fclose(in);
fclose(out);
return 0;
Категория: C++ | Добавил: shum
Просмотров: 3152 | Загрузок: 0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Это интересно!


Copyright MyCorp © 2020