TCHS 08, Раунд 3, Один, Два, Три (OneTwoThree)

Найти наименьшее число, которое делится на все числа от 1 до n. Результат вернуть по модулю 987654321.

Класс: OneTwoThree

Метод: int minimalNumber(int n)

Ограничения: 1 £ n £ 100000.

Вход. Целое число n.

Выход. Наименьшее число, которое делится на все числа от 1 до n , взятое по модулю 987654321.

Пример входа

n

3

10

97969

Пример выхода

6

2520

528039414

РЕШЕНИЕ

простые числа

В функции gen_primes при помощи решета Эратосфена присвоим prime[i] = 1, если i простое число и prime[i] = 0 иначе. Обозначим через res результат. Тогда для каждого простого i (2 £ i £ n) значение res необходимо умножать на i, i², i³, …, i^k до тех пор, пока i^k £ n. Каждое умножение следует производить по модулю 987654321.

ПРОГРАММА

#include <stdio.h>

#define MAX 100001

#define i64 long long

int prime[MAX];

void gen_primes()

{

int i,j;

for(i=0;i<MAX;i++) prime[i] = 1;

for(i=2;i*i<=MAX;i++)

if (prime[i])

for(j=i;j*i<MAX;j++) prime[i*j] = 0;

}

class OneTwoThree

{

public:

int minimalNumber(int n)

{

i64 temp;

int i,res=1;

gen_primes();

for(i=2;i<=n;i++)

if (prime[i])

{

temp = prime[i];

while(temp*i<=n) temp *= i;

res = (res * temp) % 987654321;

}

return res;

}

};