Наибольший общий делитель (НОД) двух чисел может вычислен по формуле:НОД(a,b) = a, если b = 0;НОД(a,b) =НОД(b,a%b), если b > 0, где % — остаток от деления.
Наибольший общий делитель нескольких чисел вычисляется последовательным применением НОД к парам чисел:
НОД(a,b,c) =НОД(НОД(a,b),c)НОД(a) = a
Вам дана последовательность a1,a2,…,aN. Требуется подсчитать количество различных НОД подпоследовательностей ai,ai+1,…,aj (где 1 ≤ i ≤ j ≤ N) этой последовательности.
Формат ввода
Первая строка ввода содержит одно целое число N(1 ≤ N ≤ 500000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 1018, разделенных пробелами —последовательность a1,a2,…,aN.
Формат вывода
Вывести одно целое число — количество различных значений среди gcd для всех непрерывных подпоследовательностей в заданной последовательности.
Пример 1
ВВОД
4
9 6 2 4
ВЫВОД
6
Пример 2
ВВОД
4
9 6 3 4
ВЫВОД
5
Но не суть. ответ ниже..
Так как язык программирования не указан, написал на C++
#include <iostream>
using namespace std;
int main() {
setlocale(LC_ALL, "Russian");
size_t boas, elephants, monkeys, parrots;
bool flag = false;
// Вводим данные
cout << "" << endl;
cout << "Введите длину каната" << endl;
cout << "" << endl;
cout << "Удавов: " ; cin >> boas;
cout << "Слоников: " ; cin >> elephants;
cout << "Мартышек: " ; cin >> monkeys;
cout << "Попугаев: " ; cin >> parrots;
cout << endl << endl;
// Меняем некоторых животных поменьше на животных побольше
// Например, 7 Мартышек можно представить как 1 Слоника и 3 Мартышки
monkeys += parrots / 8; parrots %= 8;
elephants += monkeys / 4; monkeys %= 4;
boas += elephants / 3; elephants %= 3;
// Теперь начинаем делить. Если При делении нужно располовинить какое-либо животное,
// лучше просто заменить его на соответствующее животное по-меньше
// Например, если канат длиной в 3 Слонёнка, то мы при делении на 2 могут возникнуть проблемы.
// А вот если заменить одного слоненка на 4 Мартышек и делить уже 2 Слоников и 4 Мартышки,
// то получится 1 Слоненок и 2 Мартышки
elephants += 3*(boas % 2); boas /= 2;
monkeys += 4*(elephants % 2); elephants /= 2;
parrots += 8*(monkeys % 2); monkeys /= 2;
if (parrots % 2) {
flag = true;
cout << "Количество попугаев НЕЧЕТНО" << endl << endl;
}
parrots /= 2;
// Вывод результата
cout << "" << endl;
cout << "Вывод длины деленного каната" << endl;
cout << "" << endl;
cout << "Удавов: " << boas << endl;
cout << "Слоников: " << elephants << endl;
cout << "Мартышек: " << monkeys << endl;
cout << "Попугаев: " << parrots; if (flag) cout << " + 0.5 (СКОРУЮ СЮДА!!)";cout << endl;
cout << endl << endl;
system("pause");
return 0;
}
#include <iostream>
#include <iomanip>
using namespace std;
bool isEven(int n) {
return 1 - abs(n % 2);
}
int main() {
setlocale(LC_ALL, "Russian");
const int k = 8;
int a[k], b[k];
cout << setw(6) << "Ai" << " | " << setw(6) << "Bi" << endl;
cout << "" << endl;
for (int i = 0; i < k; ++i) {
//Заполнение случайными числами (они будут каждый раз одними и теми же, ибо генерируются только 1 раз)
a[i] = rand() % (2 * 25000) - 25000;
b[i] = rand() % (2 * 25000) - 25000;
cout << setw(6) << a[i] << " | " << setw(6) << b[i] << endl;
}
size_t countA = 0, countB = 0;
for (int i = 0; i < k; ++i) {
if (isEven(a[i]))
countA++;
if (!isEven(b[i]))
countB++;
}
cout << endl;
cout << "Количество четных для А: " << countA << endl;
cout << "Количество НЕчетных для B: " << countB << endl;
system("pause");
return 0;
}