Программа должна ввести с консоли натуральное число [latex] n [/latex] и вывести в порядке возрастания [latex] n [/latex] первых четных натуральных чисел.
Входные данные
Натуральное число [latex] n [/latex].
Выходные данные
В одной строке через пробел [latex] n [/latex] первых четных натуральных чисел.
Тесты
№
Входные данные
Выходные данные
1
3
2 4 6
2
8
2 4 6 8 10 12 14 16
3
5
2 4 6 8 10
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
usingnamespacestd;
intmain(){
intn;
cin>>n;
for(inti=1;i<n+1;i++){
cout<<i*2<<" ";
}
return0;
}
Решение
Решением этой задачи является вывод через пробел удвоенных чисел от 1 до [latex] n [/latex].
Натуральное число $m$ называется ровным делителем числа $n$, если частное и остаток от деления $n$ на $m$ равны. По заданному натуральному числу $n$ найти количество его ровных делителей.
Входные данные
Натуральное число $n \space (1 ≤ n ≤ 10^{6})$.
Выходные данные
Выведите искомое количество ровных делителей числа $n$.
Тесты
Входные данные
Выходные данные
5
1
20
2
200
6
653
1
5982
4
Код программы
e-olymp 446. Ровные делители
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
usingnamespacestd;
intmain(){
unsignedn,q=0;
cin>>n;
for(intm=1;m<=n;m++)
if(n/m==n%m)
q+=1;
cout<<q;
return0;
}
Решение
Для решения этой задачи сперва введем переменную
q, в которой будем хранить количество ровных делителей числа $n$. Затем запустим цикл, который будет проверять каждое из чисел от $1$ до $n$ включительно, является ли оно ровным делителем. Если условие выполняется, то увеличиваем значение, хранящееся в
q на единицу. После цикла выведем искомое на экран.
Профессор из тридевятого царства решил, что посчитать сумму делителей числа $n$ до $10^{10}$ сможет любой троечник, поэтому усложнил для Кости задачу, дав числа с большим количеством цифр. Но наш герой не хотел сдаваться, уж больно он хотел стать отличником.
Костя очень просит Вас помочь ему в этом деле, ведь он помнит, как успешно Вы справились с предыдущей задачей.
Входные данные
Одно целое число $n \left(1 \leqslant n < 10^{15}\right).$
Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$
Для того, чтобы не вычислять $p_k^{\alpha_k+1}$, перепишем данную формулу в следующем виде:
$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$
Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $n.$
Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу.
Входные данные
Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$
Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$
Даны два взаимно простых натуральных числа [latex]a[/latex] и [latex]b[/latex]. Рассмотрим множество [latex]M[/latex] целых чисел, представимых в виде [latex][ax+by],[/latex]
где [latex]x[/latex] и [latex]y[/latex] — целые неотрицательные числа. Каково наибольшее целое число [latex]c[/latex], не принадлежащее множеству [latex]M[/latex]?
Входные данные
[latex]a[/latex] и [latex]b[/latex] — два взаимно простых натуральных числа.
Выходные данные
[latex]c[/latex] — наибольшее целое число c, не принадлежащее множеству [latex]M[/latex].
Нарисуем на плоскости систему координат [latex]Oxy[/latex] и сформулируем нашу задачу на геометрическом языке. Каждую пару целых чисел [latex]\left(x,y\right)[/latex] мы будем называть «целой точкой» и изображать красной точкой, если обе её координаты неотрицательны [latex]\left(x\geq0, y\geq0\right)[/latex], и синей точкой — если хотя бы одна координата отрицательна.
Взаимно простые натуральные числа [latex]a[/latex] и [latex]b[/latex] мы считаем фиксированными (для примера возьмём [latex]a=5, b=3[/latex]). Для каждого [latex]n[/latex] уравнение [latex]ax+by=n[/latex] определяет, как известно, прямую. Обозначим её через [latex]l_{n}[/latex]. Разумеется, все прямые [latex]l_{n}[/latex] параллельны друг другу. Пусть [latex]n[/latex] — целое. Будем считать прямую [latex]l_{n}[/latex] красной, если она проходит хотя бы через одну красную точку, и синей — в противном случае. Мы должны выяснить, каково наибольшее [latex]c[/latex], которому соответствует синяя прямая [latex]l_{с}[/latex], и доказать, что тогда из двух прямых [latex]l_{n}[/latex] и [latex]l_{c-n}[/latex] одна-синяя и одна-красная ([latex]n[/latex] — любое целое число).
Мы будем пользоваться в нашем решении перемещениями плоскости, которые отображают множество целых точек на себя и одновременно каждую прямую [latex]l_{n}[/latex] переводят в ту же самую или некоторую другую прямую [latex]l_{\acute{n}}[/latex] из нашего семейства. Это, во-первых, параллельные переносы на любой вектор [latex]\left(p, q\right)[/latex] с целыми [latex]p[/latex] и [latex]q:[/latex] [latex]\left(x,y\right)|\dashrightarrow \left(x+p, y+q\right),[/latex] и, во-вторых, повороты на [latex]180^{\circ}[/latex] (или, что то же самое, симетрии относительно точки) с любыми центрами [latex]\left(\frac{p}{2}, \frac{q}{2}\right)[/latex], где [latex]p[/latex] и [latex]q[/latex] — целые: [latex]\left(x,y\right)|\dashrightarrow \left(p-x, q-y\right).[/latex]
Докажем, что на каждой прямой [latex]l_{n}[/latex] целые точки встречаются через равные промежутки.
Лемма. Если [latex]\left(x_{0},y_{0}\right)[/latex] — целая точка на прямой [latex]l_{n}[/latex], то ближайшими к ней целыми точками на [latex]l_{n}[/latex] будут [latex]\left(x_{0}-b,y_{0}+a\right)[/latex] и [latex]\left(x_{0}+b,y_{0}-a\right)[/latex] ([latex]a[/latex] и [latex]b[/latex] взаимно просты).
Рассмотрим прямую [latex]l_{0}[/latex], проходящую через [latex]\left(0, 0\right)[/latex]. Пусть [latex]\left(-b_{1}, a_{1}\right)[/latex] — ближайшая к [latex]\left(0, 0\right)[/latex] целая точка [latex]l_{0}[/latex] такая, что [latex]b_{1}>0[/latex], [latex]a_{1}>0[/latex] (мы ещё не знаем, что [latex]b_{1}=b, a_{1}=a[/latex]), [latex]\left(x_{0}, y_{0}\right)[/latex] — целая точка [latex]l_{n}[/latex]. При переносе на вектор [latex]\left(x_{0}, y_{0}\right)[/latex] отрезок прямой [latex]l_{0}[/latex] от [latex]\left(0, 0\right)[/latex] до [latex]\left(-b_{1}, a_{1}\right)[/latex] перейдет в отрезок [latex]l_{n}[/latex] от [latex]\left(x_{0}, y_{0}\right)[/latex] до [latex]\left(x_{0}-b_{1}, y_{0}+a_{1}\right)[/latex] будет ближайшей к [latex]\left(x_{0}, y_{0}\right)[/latex] точкой [latex]l_{n}[/latex] сверху. Точно так же при переносе на вектор [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] — тот же отрезок прямой [latex]l_{0}[/latex] перейдёт в отрезок прямой [latex]l_{n}[/latex] от [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] до [latex]\left(x_{0}, y_{0}\right)[/latex]. Следовательно, и на этом отрезке целыми точками будут только его концы.
Отсюда уже следует, то на любой прямой [latex]l_{n}[/latex] (уесли на ней есть хоть одна целая точка) промежуток между соседними целыми точками один и тот же: [latex]a_{1}[/latex] единиц по оси [latex]Oy[/latex] и [latex]b_{1}[/latex] — по оси [latex]Ox[/latex]. Это, в частности, относится и к прямой [latex]l_{0}[/latex]. Поскольку [latex]\left(-b, a\right)[/latex] принадлежит [latex]l_{0}[/latex], то отсюда следует, что [latex]b=db_{1}, a=da_{1}[/latex], где [latex]d[/latex] — некоторое целое число. Но числа [latex]a[/latex] и [latex]b[/latex] по условию взаимно просты. Значит, [latex]d=1[/latex], то есть [latex]a=a_{1}, b=b_{1}[/latex]. Лемма доказана.
Из этой леммы следует, что каждая прямая [latex]l_{n}[/latex], где [latex]n[/latex] — целое, переходит ровно через одну точку внутри полосы [latex]0\leq x\leq b-1[/latex]. При этом, очевидно, если прямая красная, то есть где-то переходит через красную точку, то её целая точка в выделенной полосе тоже будет красной (а точка синей прямой, разумеется, синяя).
Теперь заметим, что при симетрии относительно точки [latex]\left(\frac{b-1}{2} -\frac{1}{2}\right)[/latex] [latex]\left(x,y\right)\mapsto\left(\acute{x}, \acute{y}\right) =\left(b-1-x, -1-y\right)[/latex], полоса [latex]0\leq x\leq b-1[/latex] переходит в себя, причем красные точки переходят в синие, и наоборот. Прямая [latex]l_{n}[/latex] после этой симметрии переходит в прямую [latex]l_{ab-a-b-n}[/latex]: если [latex]ax+by=n[/latex], то [latex]a\acute{x}+b\grave{y}=a\left(b-1-x\right)+b\left(-1-y\right)=ab-a-b-n.[/latex] (Через центр симметрии, где [latex]a\left( \frac{b-1}{2}\right)+b\left(- \frac{1}{2}\right) = \frac{ab-a-b}{2},[/latex] ни одна из наших прямых может и не проходить.)
Ясно, что самая нижняя красная прямая — это [latex]l_{0}[/latex]. Следовательно, самая верхняя синяя прямая — это [latex]l_{ab-a-b}.[/latex] Итак, наибольшее число, не принадлежащее множеству, — это [latex]c=ab-a-b,[/latex] и из двух чисел [latex]n[/latex] и [latex]c-n[/latex] одно принадлежит [latex]M[/latex], а другое — нет.
Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа [latex]n[/latex], [latex]m[/latex]. Получить все меньшие [latex]n[/latex] натуральные числа, квадрат суммы цифр которых равен [latex]m[/latex].
Входные данные:
Два положительных числа [latex]n[/latex] и [latex]m[/latex].
Выходные данные:
Все целые числа из [latex]\left( 0,n \right)[/latex], удовлетворяющие условию.
Для того, чтоб найти каждую цифру числа будем искать остаток от деления на [latex]10[/latex], которым является последняя цифра числа, а затем делить число нацело на [latex]10[/latex], чтоб предпоследняя цифра стала последней. Будем повторять эту операцию пока число не равно [latex]0[/latex]. Все полученные цифры числа складываем. Таким способом будем искать сумму цифр каждого целого числа от [latex]1[/latex] до [latex]n-1[/latex], параллельно возводя полученную сумму в квадрат, а результат сравнивая с [latex]m[/latex].
Даны натуральные числа [latex]n_{1},\dots,n_{m}[/latex], действительные числа [latex]x_{1},\dots,x_{m}[/latex]. Вычислить [latex]\frac{n_{1}\cdot x_{1}+\dots+n_{m}\cdot x_{m}}{n_{1}+\dots+n_{m}}[/latex].
Тестирование
№
Входные данные
Выходные данные
1.
1 2 4 -1
-0.4
2.
1 2 3 4 5 0.6
1.88889
3.
5 -2 1 0.2 3 -3 2 0
-1.70909
4.
10 3.3 4 0.4 6 0.01 8 1 1 8
1.7469
5.
3 -0.5 2 -0.4 1 -0.3 5 32 11 5 20 -1
4.58095
Реализация (класс vector)
A278
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
usingnamespacestd;
intmain(){
vector<int>n;
vector<double>x;
inta,sum2=0;
doubleb,res=0,sum1=0;
while(cin>>a>>b)
{
n.push_back(a);
x.push_back(b);
}
for(inti=0;i<x.size();i++)
{
sum1+=n[i]*x[i];
sum2+=n[i];
res=sum1/sum2;
}
cout<<res<<endl;
return0;
}
Алгоритм решения (класс vector)
Считываем все натуральные числа до конца входного потока и записываем их в вектор [latex]n[/latex]. Аналогично, считываем все действительные числа до конца входного потока и записываем их в вектор [latex]x[/latex].
Вычисляем значение выражения [latex]n_1\cdot x_1+\dots+n_m\cdot x_m[/latex], накапливая сумму
sum1.
Вычисляем значение выражения [latex]n_1+\dots+n_m[/latex], накапливая сумму
sum2.
Находим результат
res от деления
sum1 на
sum2.
Реализация (потоковая обработка)
А278
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cmath>
usingnamespacestd;
intmain()
{
intmember1,sum2=0;
doublemember2,res=0,sum1=0;
while(cin>>member1>>member2)
{
if(member1=='e')break;
sum1+=member1*member2;
sum2+=member1;
}
res=sum1/sum2;
cout<<res<<endl;
return0;
}
Алгоритм решения (потоковая обработка)
Считываем все натуральные числа до конца входного потока и записываем их в переменную
member1. Аналогично, считываем все действительные числа до конца входного потока и записываем их в переменную
member2.
Пока вводятся данные:
Вычисляем значение выражения [latex]n_1\cdot x_1+\dots+n_m\cdot x_m[/latex], накапливая сумму
sum1.
Вычисляем значение выражения [latex]n_1+\dots+n_m[/latex], накапливая сумму
sum2.
Находим результат
res от деления
sum1 на
sum2.
Для запроса на выполнение следует перейти по ссылке (класс vector).
Для запроса на выполнение следует перейти по ссылке (потоковая обработка).
Для отправки комментария необходимо войти на сайт.