Элементы теории чисел

Обмен двух переменных
c=a; a=b; b=c;
a=a+b; b=a-b; a=a-b;
a=a^b; b=a^b; a=a^b;
swap(a,b);

Теория чисел
Использование теории чисел в олимпиадах по информатике в основном касается:
общих понятий делимости и деления с остатком;
простоты чисел, простых множителей;
наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК);
моделирования арифметических операций («длинная арифметика»).

Деление с остатком
r = a / b;
q = a % b;
Указанные операции не соответствуют математическому определению в случае, когда число a отрицательное (проверьте). Кроме того, они определены и для отрицательных значений b.

Свойства остатков

Делители натурального числа

Поиск делителей числа
void divisors(int a)
{
int i;
for (i = 1; i * i < a; i++)
if (a % i == 0)
{
process(i); /*обработать делитель*/
process(a / i);
}
if (i * i == a)
process(i);
}

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

Проверка на простоту
bool isPrime(int a)
{
for (int i = 2; i * i <= a; ++i)
if (a % i == 0)
return false;
return true;
}

Решето Эратосфена

Решето Эратосфена

Решето Эратосфена
void eratosthenes(int n)
{
/* число 1 не является простым */
p[1] = false;
/* сначала все числа "не вычеркнуты" */
for (int i = 2; i <= n; ++i)
p[i] = true;
for (int i = 2; i * i <= n; ++i)
{
/* если число простое... */
if (p[i])
/*начинаем "вычeркивать" составные числа*/
for (int j = i * i; j <= n; j += i)
p[j] = false;
}
}

Простые числа можно хранить константным массивом в тексте программы:
int simple[25]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

Основная теорема арифметики

Факторизация числа

Факторизация числа
void factorization(int n)
{
int a = n; /* копия n, над которой производится деление */
int p;
for (p = 2; p * p <= n; ++p)
if (a % p == 0)
{
int c = 0; /* счетчик степени вхождения числа */
while (a % p == 0)
{
a /= p;
c++;
}
report(p, c);
}
if (a != 1)
report(a, 1);
}

Хранение числа в виде разложения
Любое число можно представить в виде произведения простых чисел. Такое представление выглядит в виде одномерного массива в каждой ячейке которого содержится степень соответствующего просто числа.
Например, пусть у нас есть массив простых чисел
[2; 3; 5; 7; 11; 13],
тогда число 2600 будет выглядеть как [3; 0; 2; 0; 0; 1]
(23 ∙ 52 ∙ 131 = 2600),
число 11858 представляется массивом [1; 0; 0; 2; 2; 0]
(21 ∙ 72 ∙ 112 = 11858)

Хранение числа в виде разложения
Такие числа легко умножать. Чтобы получить произведение чисел, достаточно сложить соответствующие элементы массивов.
[3; 0; 2; 0; 0; 1]
[1; 0; 0; 2; 2; 0]
Результатом будет массив [4; 0; 2; 2; 2; 1], т.е. 24 ∙ 52 ∙ 72 ∙ 112 ∙ 131 = 30830800 = 2600 ∙ 11858.
Можно реализовать деление с остатком, нахождение НОД и НОК.

НОД и НОК
Наибольшим общим делителем (НОД) неотрицательных целых чисел a и b (не являющихся одновременно нулями) назовем наибольший элемент множества общих делителей чисел a и b.
Общим кратным двух натуральных чисел a и b называется любое такое натуральное число c, что a делит c и b делит c. Наименьшим общим кратным (НОК) называется минимальное из таких натуральных чисел

НОД и НОК
Пусть числа заданы разложением на простые множители.
Разложение на простые множители НОД(a; b) включает в себя только те простые числа, которые встречаются в как в разложении a, так и в разложении b. При этом степень, в которой простое число входит в разложение НОД, равна минимальной из степеней, в которых число входит в разложения a и b.
НОК двух чисел состоит из тех простых множителей, которые встречаются хотя бы в одном из разложений исходных чисел, а кратность (степень) вхождения такого множителя равна максимальной из его кратностей в разложениях исходных чисел.

НОД и НОК

Свойства НОД
НОД(a; a) = a;
НОД(a; 1) = 1;
НОД(a; 0) = a:
НОД(a, b) = НОД(a – b, b)
НОД(a, b) = НОД(a mod b, b)
НОД(2a, 2b) = 2НОД(a, b)
НОД(2a, b) = НОД(a, b), если b – нечетно.

Алгоритм Евклида
int gcd (int a, int b)
{
while (b && a)
{
if (a > b)
a %= b;
else
b %= a;
}
return a + b;
}

Варианты реализации алгоритма Евклида
нахождение разностей
обмен значений
рекурсивная реализация
рекурсия с тринарным оператором
бинарная реализация
использование библиотеки

Евклид (нахождение разностей)
int gcd (int a, int b)
{
while (b!=a)
{
if (a>b)
a -= b;
else
b -= a;
}
return a;
}

Евклид (обмен значений)
int gcd (int a, int b)
{
while (b)
{
a %= b;
swap (a, b);
}
return a;
}

Евклид (рекурсивная реализация)
int gcd (int a, int b)
{
if (b == 0)
return a;
else
return gcd (b, a % b);
}

Евклид (рекурсия с тринарным оператором)
int gcd (int a, int b)
{
return b ? gcd (b, a % b) : a;
}

Евклид (бинарная реализация)
int gcd (int a, int b)
{
int c = 1;
while (b && a)
{
unsigned int d = b & 1;
if (!(a & 1))
if (!d)
{
a >>= 1; b >>= 1; c <<= 1;
}
else a >>= 1;
else
if (!d) b >>= 1;
else
if (a > b)
a %= b;
else
b %= a;
}
return (a + b) * c;
}

Евклид (использование библиотеки)
#include
#include
#include
using namespace std;
int main()
{
cout << __gcd(78,56) << endl;
return 0;
}

Функция Эйлера

Свойства функции Эйлера

Вычисление функции Эйлера

Вычисление функции Эйлера
int phi (int n)
{
int result = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
{
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}

Ввод – Вывод на C++
#include
using namespace std;
int main()
{
freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
int a,b;
scanf("%d%d", &a, &b);
printf("%d", a + b);
return 0;
}
#include
using namespace std;
int main()
{
ifstream fin("input.txt");
ofstream fout("output.txt");
int a, b;
fin >> a >> b;
fout << a + b;
return 0;
}

Универсальный" код, который работает правильно под обеими системами, может выглядеть так:
#ifdef WIN32
printf("%I64d\n",ans);
#else
printf("%lld\n",ans);
#endif

ios_base::sync_with_stdio(0);
Для ускорения ввода-вывода при использовании потокового ввода-вывода
Не использовать вместе с:
freopen
#include