Целочисленная арифметика

Знание свойств чисел и математических выражений зачастую помогает решить задачи информатики существенно проще. Например, задача о нахождении количества цифр целого неотрицательного числа обычно сводится к последовательному делению нацело на 10 с помощью цикла. В главе «Рекурсия» данного пособия мы рассматриваем рекурсивную модификацию этого же метода, который, несмотря на то, что записывается в одну строку, реализуется фактически тем же способом. Альтернативное решение можно получить, воспользовавшись свойством десятичных логарифмов.

#include <iostream>

#include <cmath>

int main(){

unsigned int x, cnt_digit;

std::cin >> x;

cnt_digit = log10(x) + 1;

std::cout << cnt_digit;

}

При решении задач со свойствами чисел порой бывает удобно использовать функцию floor(). Функция floor() возвращает округлённое значение, которое не больше изначального аргумента. Например,для float x = 2.8345:

cout << floor(x * 100) / 100;

Выведет 2.83. При этом:

cout << floor(x * 1000) / 1000;

Выведет 2.834.

Задача №207.  Делимость на 11

Для делимости числа на 11 необходимо, чтобы разность между суммой цифр, стоящих на четных местах, и суммой цифр, стоящих на нечетных местах, делилась на 11.

Требуется написать программу, которая проверит делимость заданного числа на 11.

Входные данные

Входной файл INPUT.TXT содержит одно натуральное число N, делимость которого надо проверить (1 <= N <= 10¹⁰⁰⁰⁰).

Выходные данные

В выходной файл OUTPUT.TXT выведите “YES”, если число делится на 11, или “NO” иначе.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	121	YES
2	1211	NO

Решение

#include <iostream>

#include <string>

using namespace std;

int even, odd, i;

 

int main() {

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

string a;

cin >> a;

for(i = 0; i < a.length();i++)

     if(i % 2)even+=a[i]-'0';

     else odd += a[i]- '0';

cout << ((odd-even) % 11 == 0 ? "YES" : "NO");

return 0;

}

Задача №208.  Разложение числа (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Любое натуральное число можно представить в виде суммы нескольких последовательных натуральных чисел. Например, число 25 можно представить в виде суммы из одного (25), двух (12+13) или пяти (3+4+5+6+7) чисел.

Требуется написать программу, которая определит максимальное количество чисел в таком разложении.

Входные данные

Входной поток содержит одно натуральное число N (1 ≤ N ≤ 10⁹).

Выходные данные

Выходной поток должен содержать одно натуральное число – максимальное количество чисел в разложении числа N на сумму последовательных натуральных чисел.

Примеры

№	Ввод	Вывод
1	2	1
2	5	2
3	25	5

Решение

Очевидно, что переборное решение для больших значений величины N не сможет быть выполнено по TL. С другой стороны, число N должно являться суммой M членов некоторой арифметической прогрессии с шагом d = +1. Воспользуемся формулой:

где a₁ – первый член прогрессии. Отсюда

и далее

При этом a₁ должно быть целым. Попробуем оценить величину M сверху. Очевидно, M² < 2N.

#include <iostream>

#include <cmath>

using namespace std;

main(){

int n, m;

cin >> n;

for(m = sqrt(n + n); (n + n - m*m + m) % (m + m); m--);

cout << m;

return 0;

}

Задача №209.  Забавная игра (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Источник задачи: Московская олимпиада по информатике 2002/2003 г.

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 19₁₀ = 1*2⁴+0*2³+0*2²+1*2¹+1*2⁰ в двоичной системе запишется как 10011₂.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:

10011
11001
11100
01110
00111
10011

…

и результатом игры, следовательно, окажется число 1*2⁴+1*2³+1*2²+0*2¹+0*2⁰ = 28.

Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.

Входные данные

Одно целое число N (0 ≤ N ≤ 32767).

Выходные данные

Одно целое число, равное результату игры.

Примеры

№	Ввод	Вывод
1	19	28
2	1212	1938

Решение

Применим двоичную арифметику для решения данной задачи. Вначале определим k - количество значащих цифр в двоичной записи числа n. Все разряды имеют номера от 0 до sizeof( n)-1, где sizeof( n)–количество байт, выделяемое для переменной n. Циклом будем двигаться от старшего разряда к младшему, пока не найдём единицу или не окажемся в нулевом разряде.

Назовём маской(mask) число, состоящее ровно из k единиц в двоичной системе

      

Например, для 101011 маска будет равна 111111.

Когда мы определили k, нужно реализовать последовательно k-1 циклических сдвигов на 1 разряд. Каждый сдвиг реализуется тремя побитовыми операциями

1. Побитовый сдвиг (нециклический) на 1 разряд влево

n <<= 1

Например, число 101011 преобразуется в 1010110

2. Запись в младший разряд n₀цифры из k-го разряда n_k.

n |= (n>>k) & 1

Например, число 1010110 после побитовой дизъюнкции с единицей (00…001) преобразуется в 1010111

3. Удаление всех двоичных цифр, выходящих за маску

n &= mask

Например, 1010111 & 111111 = 010111

#include<iostream>

#define D ((n>>k)&1)      // k-я цифра в двоичной записи n

int main() {

int n, k = sizeof(n)*8-1, i, m, mask;

std::cin>>n;

for(; !D&& ~k; --k);  // находим старший ненулевой разряд

mask = (1 <<++k) - 1;

m = n;

for(i=1; i<k; i++){   // перебираем все циклические сдвиги

   ((n <<= 1) |= D) &= mask;

   if(n > m) m = n;

}

std::cout << m;

}

Задача №210.  Двоичная машина (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

На вход некоторой двоичной машине подается n-разрядное двоичное число. Машина подвергает поданное число следующим преобразованиям:

1. Записывает исходное число в регистры A и B размером N двоичных разрядов (бит).

2. N-1 раз выполняет следующие действия: циклически сдвигает регистр B на один бит влево (при этом самый старший бит переходит в самый младший); прибавляет к значению регистра A значение регистра B по модулю 2^N .

3. К регистру A применяется побитовая операция логического отрицания

4. К регистру A прибавляется 1 по модулю 2^N.

5. Значение регистра A выдается в качестве результата c отбрасыванием ведущих (незначащих) нулей.

Например, если на вход машине подать число 1001, то будут выполнены следующие преобразования:

№ шага	A	B	Result
1.	1001	1001
2. (повтор. 1)	1100	0011
2. (повтор. 2)	0010	0110
2. (повтор. 3)	1110	1100
3.	0001	1100
4.	0010	1100
5.	0010	1100	10

Напишите программу, которая по заданному числу возвращает результат преобразования согласно описанному алгоритму работы двоичной машины.

Входные данные

Первая строка входного файла INPUT.TXT содержит число N – количество двоичных разрядов (N <= 100 000). Вторая строка содержит ровно N двоичных разрядов (нулей или единиц) – входное число.

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ – результат преобразования в двоичном виде без ведущих нулей.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	4 1001	10
2	7 1101101	101

Решение

Рассмотрим все поразрядные сдвиги исходного представления числа на любом примере

Исходное число (разряд А), N=5	1	1	0	0	1
Сдвиг B1	1	0	0	1	1
Сдвиг B2	0	0	1	1	1
Сдвиг B3	0	1	1	1	0
Сдвиг B4	1	1	1	0	0

Очевидно, что при суммировании по модулю 2Nвсех этих значений в каждом столбце будет ровно Kединиц, где K – количество единиц в исходном числе. При этом порядок их взаимного расположения значения не имеет. Легко увидеть, что, например

N=4		N=5		N=6
K	Сумма	K	Сумма	K	Сумма
0	0000	0	00000	0	000000
1	1111	1	11111	1	111111
2	1110	2	11110	2	111110
3	1101	3	11101	3	111101
4	1100	4	11100	4	111100
		5	11011	5	111011
				6	111010

и т.д. Сумму легко посчитать для любого Nи Kпо формуле

Однако этого не требуется, если учесть, что полученную сумму нужно инвертировать, что даст ответ K-1. А затем к сумме по условию задачи нужно добавить 1. В итоге, задача свелась к выводу двоичной записи числа K.

#include <fstream>

using namespace std;

int main(){

ifstream cin("input.txt");

ofstream cout("output.txt");

char ch;

int k=0, n;

cin >> n;

for(int i = 0; i < n; i++) {

   cin >> ch;

   k += ch-'0'; //считаем количество единиц K

}

if(!k) cout << '0'; //выводим двоичное представление K  

else {

   string s = "";

   while(k>0){

       ch = '0' + k%2;

       s = ch + s;

       k/=2;

   }

   cout << s;

}

}

Задача №211.  Египетские знаки(acmp.ru)

Прошлым летом школьник Вася побывал в Египте. И лишь сейчас он вспомнил, что во время своей поездки он успел сфотографировать много интересностей. Перебирая эти фотографии, больше всего он заинтересовался видами пирамид в Гизе. Пирамиды, помимо всяких иероглифов, содержали удивительные знаки - 1, 2, 3, 4, 5, 6, 7, 8, 9, 0. Внимательно присмотревшись Вася заметил, что каждая строка таких странных символов является степенью двойки и более того первая строка начинается последовательностью символов 1, вторая - 2, ..., сто двадцатая - 120, и т.д. Но все было бы хорошо, если бы Вася пользовался современными фотоаппаратами, поэтому его старенькая мыльница плохо сфотографировала наиболее освещенные части пирамиды, поэтому все символы разобрать невозможно и определить показатель степени двойки, соответствующий таким строкам, затруднительно.

Вася задумался о восстановлении символов и, наконец, решил попросить кого-нибудь написать программу (Вася учится в 6 классе и не знает языков программирования), которая бы определила показатель степени двойки, которая записана в N-ой строке.

Входные данные

Единственное число N<=10⁷.

Выходные данные

Выведите минимальное натуральное число K такое, что 2^K в десятичной записи начинается c числа N, или если Вася что-то напутал, и такого числа нет, выведите -1.

Примеры

№	Ввод	Вывод
1	12	7
2	134	27
3	82	209

Пояснение

Пример №1: 2⁷=128

Пример №2: 2²⁷=134217728

Решение

#include <iostream>

#include <cmath>

using namespace std;

int main(){

int n, k = 0;

cin >> n;

double q = log10(2.0), w = log10(n),

       e = log10(n+1), x;

do{

   x = k*q - w;

   if(x>=0 && floor(x)>k*q - e) break;

   k++;

} while(true);

cout<<k;

}

Задача №212.  Система счисления Фибоначчи(acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Числа Фибоначчи F₁, F₂, … определяются начальными значениями и соотношением:

                              F₁=1; F₂=2; F_n=F_n-1+F_n-2.

Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы, весами являются не степени двойки 1, 2, 4, 8, 16, …, а числа Фибоначчи 1, 2, 3, 5, 8, 13, …. В этой системе счисления каждое положительное целое число единственном способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.

Требуется написать программу, которая по двум заданным строкам, представляющим числа A и B в системе счисления Фибоначчи, находила строку, представляющую число A+B также в этой системе счисления.

Например, исходные строки 10101 и 100 представляют числа 1*8+0*5+1*3+0*2+1*1=8+3+1=12 и 1*3+0*2+0*1=3. Ответом является строка 100010, представляющая число 1*13+0*8+0*5+0*3+1*2+0*1=13+2=15=12+3.

Входные данные

В первой строке содержится число A и B во второй. Длина записи чисел A, B и их суммы A+B в системе счисления Фибоначчи не превышает 255 знаков.

Выходные данные

Выведите значение суммы A+B в системе счисления Фибоначчи.

Пример

Ввод	Вывод
10101 100	100010

Решение

Решение данной задачи предполагает два основных подхода. Первый состоит в том, чтобы перевести число в позиционную систему счисления, затем выполнить операцию суммированию, после чего жадным алгоритмом (каждый раз брать наибольшее число Фибоначчи, не превышающее данное) перевести обратно в фибоначчиеву систему. В таком случае задача решалась бы с применением длинной арифметики.

Попробуем пойти другим путём – будем выполнять все операции непосредственно в фибоначчиевой системе счисления. Главная сложность заключается в том, что при суммировании, в отличие от классических позиционных систем счисления, могут изменяться не только текущий разряд и следующие, но и предыдущие. Кроме этого нужно учесть, что двеединицы не могут идти подряд.

Итак, сформулируем основные правила для разрядов суммы:

· 011 = 100

· 01 + 01 = 02 = 10

· 010 + 010 = 020 = 101

· 0100 + 0100 = 0200 = 1001

· 003 = 100

· 0030 = 1001

· 00300 = 10001

· 003000 = 100010

Легко доказать, что для двух правильно записанных чисел в фибоначчиевой системе счисления сумма ни в одном разряде не может превышать 3. Для двойки в разряде i происходит увеличение i+1 и i-2 разрядов. Для тройки в разряде i происходит увеличение в i+2 и i-2 разрядах. В обоих случаях i-2 разряд увеличивается только если i>0.

#include <iostream>

#define SIZE 256

using namespace std;

 

int main() {

string a, b;

short x, y, al, bl, i, j, c[SIZE];

cin >> a >> b;

al = a.size() - 1;

bl = b.size() - 1;

for(i = 0; i < SIZE; i++){  // суммирование по разрядам

   x = i > al ? 0 : a[al-i] - '0';

   y = i > bl ? 0 : b[bl-i] - '0';

   c[i] = x + y;

}

for(i = 0; i < SIZE; i++){

   if(i && c[i]*c[i-1]==1) { // проверка 2-х единиц подряд

       c[i] = c[i-1] = 0;

       c[i+1]++;

   }

   if(c[i]>1){             // проверка двоек и троек

       c[i + c[i] - 1]++;

       c[i] = 0;

       if(i){

           j = max(i-2, 0);

           c[j]++;

           i = j-1;

       }

   }

}

for(j = SIZE - 1; !c[j]; j--); //

for(i = j; i >= 0 ; i--) cout << c[i];

}

Задача №213.  Лампочки

(Время: 2 сек. Память: 16 Мб)

Имеется ряд из N лампочек, которые пронумерованы от 1 до N. Изначально ни одна из лампочек не горит. Далее происходит K последовательных линейных инверсий этого ряда ламп. Под линейной инверсией понимается инверсия каждой P-й лампочки в ряде. Например, если P=3, то произойдет инверсия 3й, 6й, 9й и т.д. лампочек.

Требуется определить: сколько горящих лампочек останется после реализации всех заданных линейных инверсий?

Входные данные

В первой строке заданы числа N и K – число лампочек и число линейных инверсий.Вторая строка состоит из K целых чисел Pi, задающих период данных инверсий. (1 ≤ N ≤ 10⁹, 1≤K≤100, 1 ≤ P_i≤ 50)

Выходные данные

Одно число - ответ на задачу.

Примеры

№	Ввод	Вывод
1	20  3 2  3  8	8
2	172  10 19  2  7  13  40  23  16  1  45  9	99

Решение

Несмотря на кажущуюся простоту, это весьма сложная задача ввиду ограничений на величину N. Массив на миллиард лампочек для непосредственного моделирования привёдёт к невозможности уложиться как по времени, так и по памяти.

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

После применения первой инверсии P1, будут гореть N/P1 (деление нацело) лампочек.

После второй инверсии будут гореть:

лампочек (находим, сколько зажигает лампочек каждая инверсия по отдельности, и вычитаем из этого количества лампочки, попадающие в обе инверсии).

Для третьей инверсии:

И т.д. Или в общем виде

где U–НОК каких-то чисел, а V– коэффициент, на который умножается дробь.

Для K инверсий таких слагаемых будет 2^K-1, что при больших K приведёт к превышению лимита времени. Однако количество слагаемых можно существенно сократить, если не учитывать слагаемые, в которых НОК получается больше N. Очевидно, что такие слагаемые равны нулю, а значит, их и следующие слагаемые, полученные умножением на них, можно исключить.

Для хранения таких пар удобно использовать ассоциативный массив map A, который содержит пары «ключ-значение», где в роли ключа будет выступать U, а значения V. Обращаться к элементам U : Vтакого массива можно в форме U : A[U] или A->first : A->second.

Изначально этот ассоциативный массив пуст. Первыми элементами, которые мы добавим, будут

Ai->first = i Ai->second = 1

Для всех других уже существующих пар

Ai->first = НОК(i, Uj) Ai->second = -2 * Vj

Код

#include <iostream>

#include <map>

#define MAXP 50

using namespace std;

 

typedef map<int, int> arr;     // ассоциативный массив U : V

 

bool p[MAXP];

int n, k, r, i;

 

int gcd(int x, int y){          // НОД по методу Евклида

do{

   if(x>y) x %= y;

   else y %= x;

} while(x*y);

return x + y;

}

 

long long lcm(int x, int y) {   //НОК через НОД

return 1LL * x * y / gcd(x, y);

}

 

void add(arr &t, int key, int val){ // добавление элемента key:val

t[key] += val;              // в ассоциативный массив t

if(!t[key]) t.erase(key);   // избавляемся от нулей

}

 

int main(){

arr a;                // пустой ассоциативный массив

cin >> n >> k;

while (k--){                     // читаем инверсии

   cin >> i;

    p[--i] ^= 1;            // xor с 1 равносилен инверсии

}

for (i = 0; i < MAXP; )

   if (p[i++]) {

       arr b(a);                // вспомогательный массив

       for(arr::iterator it = a.begin(); it != a.end(); ++it) {

           long long l = lcm(it->first, i);

           if (l <= n) add(b, l, -2 * it->second);

       }

       swap(a, b);         // обновляем массив

       add(a, i, 1);

   }

for (arr::iterator it = a.begin(); it != a.end(); ++it)

   r += (n / it->first) * it->second;

cout << r;

}

 

Длинная арифметика

Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами больших величин, чем это возможно для стандартных типов данных.

Работая с «длинными» числами, чьи значения выходят за диапазон стандартных типов, нам придётся для них рассмотреть несколько важных операций, которые для базовых типов реализованы средствами языка[37]:

1. Ввод и вывод;

2. Сложение;

3. Вычитание;

4. Сравнение;

5. Полудлинное умножение – умножение «длинного» числа на «короткое»;

6. Длинное умножение – умножение «длинного» на «длинное»;

7. Полудлинное деление – деление «длинного» числа на «короткое»;

8. Длинное деление – умножение «длинного» на «длинное».

Рассмотрим несколько представлений «длинных» целых чисел с помощью массива.

19.1 Упрощенная модель «число=строка»

Является частным случаем следующей модели 10^ n при n=1.

Первая наиболее интуитивно понятная модель – представление длинных чисел с помощью массива символов (строки). В данной модели нам нужно лишь посимвольно производить хорошо известные нам операции с разрядами десятичного числа.

ВАЖНО: Данная модель является наиболее простым представлением длинных чисел, хотя и медленным в работе. Она удобна для решения задач с большим TIMELIMIT, а также для улучшения понимания более сложных моделей. Также её хорошо использовать, если, к примеру, нужно определить, встречается ли в записи числа 3 идущих подряд нуля и т.д. – это достаточно просто выполняется строковыми функциями.

Задача №214.  Золото племени АББА (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Главный вождь племени Абба не умеет считать. В обмен на одну из его земель вождь другого племени предложил ему выбрать одну из трех куч с золотыми монетами. Но вождю племени Абба хочется получить наибольшее количество золотых монет. Помогите вождю сделать правильный выбор!

Входные данные

Три натуральных числа через пробел. Каждое из чисел не превышает 10¹⁰⁰.

Выходные данные

Одно целое число — максимальное количество монет, которые может взять вождь.

Примеры

№	Ввод	Вывод
1	5 7 3	7
2	987531 234 86364	987531
3	189285 283 4958439238923098349024	4958439238923098349024

Решение

Данную задачу можно решить без алгоритмов длинной арифметики, используя лишь строковые функции. Из двух чисел больше то, в котором разрядов больше. Если количество разрядов совпадает, то сравнение чисел эквивалентно лексикографическому сравнению строк.

#include <iostream>

using namespace std;

string smax(string x, string y){

int m = x.size(), n = y.size();

if(m > n) return x;

if(m < n) return y;

return max(x, y);

}

int main(){

string a, b, c;

cin >> a >> b >> c;

cout << smax(a, smax(b, c));

}