eolymp
bolt
Try our new interface for solving problems
Məsələlər

Отчёт 3

Отчёт 3

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Участники Международной летней школы по программированию 2011 года в Севастополе должны помнить о том, как однажды один финансист задумался над следующим вопросом - возможно ли имея отрицательные суммарные показатели по каждому интервалу месяцев одной и той же длины некоторого отчетного периода, тем не менее, по суммарным итогам этого же отчетного периода иметь положительный показатель.

Благодаря помощи, оказанной участниками школы при решении этого вопроса, выснилось, что для некоторых N можно найти такие n, для которых существует последовательность длины N, сумма членов которой положительна, но каждый отрезок длины n в сумме дает отрицательное число. Напримет, для N=5 можно взять n=2, а в качестве последовательности взять 4, -5, 4, -5, 4. Совершенно очевидно, что аналогично можно добиться и обратного эффекта. Т.е. составить последовательность длины N, сумма членов которой отрицательно, несмотря на то, что каждый отрезок длины n в сумме дает положительное число. Поэтому такие n будем называть опасными по отношению к N, соответственно все остальные числа будем называть безопасными по отношению к N. Уточним, что нас будут интересовать числа, не превосходящие N.

В некотором Регионе уровень демократии так высок, что каждая организация имеет право самостоятельно определить для себя величину отчетного периода. Более того, известно, что желая самоутвердиться, организации в обязательном порядке подбирают для себя уникальные числа в качестве величины отчетного периода.

В этом Регионе два периода N и M принято называть конкурирующими, если у них есть хотя бы одно общее безопасное число, превосходящщеее 1. Соответственно, организации с конкурирующими величинами отчетных периодов также принято называть конкурирующими.

Региональная служба корпоративного развития просит Вас составить программу, которая по заданной величинне отчетного периода N (1N2*10^10) некоторой организации определит максимально возможное количество организаций не являющихся конкурирующими с данной организацией из числа имеющих период, не превосходящий N при условии, что период – это целое число, не меньшее, чем 2.

Giriş verilənləri

Единственная строка входного файла содержит число N.

Çıxış verilənləri

В выходном файле единственное число – ответ задачи.

Nümunə

Giriş verilənləri #1
1000007
Çıxış verilənləri #1
965495
Mənbə III Международная Летняя школа программирования 2012 г. Севастополь