e-olymp 9405. Профессор и шары

19/09/2020 by Аліна Малихіна

Условие задачи

Для праздника Профессор купил голубые, красные и жёлтые воздушные шары. Всего $n$ штук. Жёлтых и голубых вместе — $a$. Красных и голубых — $b$ штук.

Сколько голубых, красных и жёлтых шаров купил Профессор?

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

Три натуральных числа $n$, $a$, $b$.

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

В одной строке выведите количество голубых, красных и жёлтых шаров, которые купил Профессор.

Тесты

№	Входные данные	Выходные данные
1	10 6 8	4 4 2
2	12 8 10	6 4 2
3	14 10 12	8 4 2
4	16 14 12	10 2 4

Программный код

public class Main
{
	public static void main(String[] args) {
		java.util.Scanner Javain = new java.util.Scanner(System.in);
	    int n, a, b, blue, yellow, red; 
        n = Javain.nextInt();
        a = Javain.nextInt();
        b = Javain.nextInt(); 
        blue = b + a - n; //считаем кол-во синих шаров
        red = b - blue; //считаем кол-во красных шаров
        yellow = a - blue; //считаем кол-во жёлтых шаров
        System.out.print(blue + " " + red + " " + yellow); 
	}
}

public class Main

{

public static void main(String[] args) {

java.util.Scanner Javain = new java.util.Scanner(System.in);

int n, a, b, blue, yellow, red;

n = Javain.nextInt();

a = Javain.nextInt();

b = Javain.nextInt();

blue = b + a - n; //считаем кол-во синих шаров

red = b - blue; //считаем кол-во красных шаров

yellow = a - blue; //считаем кол-во жёлтых шаров

System.out.print(blue + " " + red + " " + yellow);

}

Решение

Для решения задачи необходимо вывести формулу для вычисления количества жёлтых ($y$), синих ($u$) и красных ($r$) шаров. Из условия имеем, что:

$$\left.\begin{matrix}
&u&+&y&=a&\\
&r&+&u&=b&\\
&r&+&u&+&y&=n&
\end{matrix}\right\}$$

Выразим $r$ и $y$ через $u$:

$$\left.\begin{matrix}
r=&b&-&u&\\
y=&a&-&u&
\end{matrix}\right\}$$

Подставим эти значения в формулу $r+u+y=n$:

$n=b-u+u+a-u$

$u$ и $-u$ взаимоуничтожатся и мы получим, что:

$n=a+b-u$

Теперь выведем формулу для вычисления количества синих шаров:

$u=b+a-n$

Ссылки

Задача на e-olymp
Код программы на Ideone
Засчитанное решение

e-olymp 913. Используй подпрограмму

30/05/2019 by Никита Пушкин

Задача

Вычислить сумму и произведение $n$ пар заданных вещественных чисел, воспользовавшись подпрограммой $SumDob$ для вычисления суммы и произведения двух вещественных чисел.

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

В первой строке задано натуральное число $n$ — количество пар чисел. В последующих $n$ строках через пробел задано по $2$ вещественных числа. Все входные данные по модулю не превышают $100$.

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

В $n$ строках вывести через пробел по два числа: сначала сумму, а потом произведение очередной пары чисел. Результат выводить с точностью $4$ знака после десятичной точки.

Тесты

#	Входные данные	Выходные данные
1	2 6 7.5 2.1 2.0	13.5000 45.0000 4.1000 4.2000
2	4 2 5 3 5 4 5 5 5	7.0000 10.0000 8.0000 15.0000 9.0000 20.0000 10.0000 25.0000
3	2 100 100 56 65	200.0000 10000.0000 121.0000 3640.0000
4	6 10 10 20 20 40 40 50 50 70 70 80 80	20.0000 100.0000 40.0000 400.0000 80.0000 1600.0000 100.0000 2500.0000 140.0000 4900.0000 160.0000 6400.0000
5	1 2 2	4 4

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception 
	{
		int n;
		Scanner in = new Scanner (System.in);
		n = in.nextInt();
		for(int i = 0; i < n; i++){
			double a, b;
			a = in.nextDouble();
			b = in.nextDouble();
			System.out.printf("%.4f", SumDob(a, b)[0]);
			System.out.printf(" ");
			System.out.printf("%.4f", SumDob(a, b)[1]);
			System.out.println();
		}
	}
	static double[] SumDob(double x, double y) {
		return new double[] {x + y, x * y};
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

int n;

Scanner in = new Scanner (System.in);

n = in.nextInt();

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

double a, b;

a = in.nextDouble();

b = in.nextDouble();

System.out.printf("%.4f", SumDob(a, b)[0]);

System.out.printf(" ");

System.out.printf("%.4f", SumDob(a, b)[1]);

System.out.println();

}

static double[] SumDob(double x, double y) {

return new double[] {x + y, x * y};

}

Решение

Как и было указано в условии задачи, при решении задачи использовалась подпрограмма $SumDob$, которая возвращает сумму и произведение двух вещественных чисел $a$ и $b$. Потом мы с помощью цикла выводим пару чисел, полученных из подпрограммы $SumDob$ $n$ раз с $n$ пар введенных значений.

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 1872. Снеговики

27/12/2018 by Дима Мороз

Задача

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин «Интернет-магазин аппаратов клонирования» аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

либо добавляет ему сверху один шар;
либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

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

Первая строка содержит количество действий $n (1 ≤ n ≤ 200000)$. В строке номер $i + 1$ содержится описание действия:

$t m$ — клонировать снеговика номер $t (0 ≤ t < i)$ и добавить сверху шар массой $m (0 < m ≤ 1000)$;
$t 0$ — клонировать снеговика номер $t (0 ≤ t < i)$ и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия $i$, описанного в строке $i + 1$ создается снеговик номер $i$. Изначально имеется пустой снеговик с номером ноль.

Все входные числа целые.

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

Выведите суммарную массу построенных снеговиков.

Тесты

Входные данные	Выходные данные
8 0 1 1 5 2 4 3 2 4 3 5 0 6 6 1 0	74
4 0 3 1 2 2 1 1 1	18
2 0 1 1 5	7
5 1 2 3 4 5 5 1 7 5 6	26

Код задачи

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), count = 0, t, m;
		int a[][] = new int[n + 1][2];
		a[count][1] = 0;
		a[count][0] = -1;
		count++;
		long sumr = 0;
		for(int i = 0; i < n; i++){
			t = in.nextInt();
			m = in.nextInt();
			if(m == 0){
				a[count][1] = a[a[t][0]][1];
				a[count][0] = a[a[t][0]][0];
			}else{
				a[count][1] = a[t][1] + m;
				a[count][0] = t;
			}
			sumr += a[count][1];
			count++;
		}
		System.out.println(sumr);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), count = 0, t, m;

int a[][] = new int[n + 1][2];

a[count][1] = 0;

a[count][0] = -1;

count++;

long sumr = 0;

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

t = in.nextInt();

m = in.nextInt();

if(m == 0){

a[count][1] = a[a[t][0]][1];

a[count][0] = a[a[t][0]][0];

}else{

a[count][1] = a[t][1] + m;

a[count][0] = t;

}

sumr += a[count][1];

count++;

}

System.out.println(sumr);

}

Решение задачи

Считываем n — количество действий. Задаем двухмерный массив размером [n+1][2] . Указываем значение первого элемента равное $0$ и нулевого элемента равного $-1$, чтобы он ни на что не ссылался в начале. В цикле считываем номер снеговика, которого нужно клонировать и массу шара, которую нужно добавить. Если масса шара равна $0$, то мы клонируем снеговика и убираем последний его шар, ссылаясь на снеговика в котором этого шара еще не было. Если же масса шара не равно $0$, то мы клонируем снеговика и добавляем ему шар массой $m$. Во второй ячейке указываем предка с которого строится новый снеговик. Выводим общую массу снеговиков.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 313. A + B

27/12/2018 by Даниил Крутоголов

A + B

Пете задали домашнее задание: найти сумму 2-х натуральных чисел A и B.

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

В первой строке задано количество заданных Пете примеров N, а далее следует N строк в формате A+B, где A и B — 2 заданных натуральных числа, между ними без пробелов символ выполнения действия сложения «+».
Соответствие входных данных указанному формату гарантируется (см. пример входных данных). Входные данные не превышают $10^{500}$. $(0 < N <= 250)$

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

В N строках вывести искомые суммы.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	$2$ $5+3$ $14818641113280510+52467$	$8$ $14818641113332977$
2	$1$ $0+0$	$0$
3	$3$ $1+1$ $1+2$ $1+3$	$2$ $3$ $4$
4	$2$ $123123123 + 321321321$ $321321321 + 123123123$	$444444444$ $444444444$

Код программы

import java.util.Scanner;
import java.math.BigInteger;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		scan.nextLine();
		while(n-- > 0){
			String s = scan.nextLine();
			int k = s.indexOf('+');
			System.out.println(new BigInteger(s.substring(0, k)).add(new BigInteger(s.substring(k+1))));
		}
	}
}

import java.util.Scanner;

import java.math.BigInteger;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

scan.nextLine();

while(n-- > 0){

String s = scan.nextLine();

int k = s.indexOf('+');

System.out.println(new BigInteger(s.substring(0, k)).add(new BigInteger(s.substring(k+1))));

}

Решение задачи

Для решения данной задачи будем использовать класс BigInteger, поскольку в наших вычислениях могут получиться числа, превышающие максимальное значение класса Long. k-тым элементом обозначим символ «+». Далее, складываем все элементы до k-того элемента и после него, переводя эти числа в объект класса BigInteger.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Сумма делителей

23/12/2018 by Алиса Ворохта

Данная задача является упрощенным вариантом задания олимпиады KPI-OPEN 2018.

Задача

Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $n.$
Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу.

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

Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные	Выходные данные
$12$	$28$
$239$	$240$
$1234$	$1854$
$6$	$12$
$1000000007$	$1000000008$
$44100$	$160797$
$223092870$	$836075520$
$2147483648$	$4294967295$
$678906$	$1471002$
$1111111$	$1116000$
$9876543210$	$27278469036$
$99460729$	$99470703$
$5988$	$14000$
$1$	$1$
$1348781387$	$1617960960$
$135792$	$406224$
$5402250$	$17041284$
$375844500$	$1259767236$
$1000000000$	$2497558338$
$2357947691$	$2593742460$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long sumOfDivisors = 1;
		Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        HashMap<Long, Long> primeDivInPow = new HashMap<>();
        for(long i = 2; i * i <= n; i++){
	        while(n % i == 0){
	            if(primeDivInPow.containsKey(i) == false){
	                primeDivInPow.put(i, (long) 1);
	            }
	            primeDivInPow.put(i, primeDivInPow.get(i) * i);
	            n /= i;
	        }
        }
        if(n != 1){
        	primeDivInPow.put(n, n);
		}
		for (Map.Entry<Long, Long> entry : primeDivInPow.entrySet()) {
			 sumOfDivisors *= (entry.getValue() * entry.getKey() - 1) / (entry.getKey() - 1);
		}
		System.out.println(sumOfDivisors);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

long sumOfDivisors = 1;

Scanner in = new Scanner(System.in);

long n = in.nextLong();

HashMap<Long, Long> primeDivInPow = new HashMap<>();

for(long i = 2; i * i <= n; i++){

while(n % i == 0){

if(primeDivInPow.containsKey(i) == false){

primeDivInPow.put(i, (long) 1);

}

primeDivInPow.put(i, primeDivInPow.get(i) * i);

n /= i;

}

if(n != 1){

primeDivInPow.put(n, n);

}

for (Map.Entry<Long, Long> entry : primeDivInPow.entrySet()) {

sumOfDivisors *= (entry.getValue() * entry.getKey() - 1) / (entry.getKey() - 1);

}

System.out.println(sumOfDivisors);

}

Решение задачи

Пусть $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}.$$

Ссылки

Код решения

e-olymp 1000. Задача a + b

17/12/2018 by Саша Рябова

Задача

Вычислите сумму $a+b$.

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

В каждой строке задано два целых числа $a$ и $b$ $(|a|,|b| \leq 30000)$.

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

Для каждого теста выведите сумму $a+b$ в отдельной строке.

Тесты

Входные данные	Выходные данные
$4$ $8$ $5$ $0$ $-6$ $8$	$12$ $5$ $2$
$-3$ $3$	$0$
$12$ $8$ $10$ $10$	$20$ $20$
$30000$ $30000$ $3000$ $3000$ $300$ $300$ $30$ $30$ $3$ $3$	$60000$ $6000$ $600$ $60$ $6$
$10$ $23$ $613$ $2$ $-200$ $300$	$33$ $615$ $100$

Код программы

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()){
        	int a = in.nextInt();
        	int b = in.nextInt();
        	System.out.println(a+b);
		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

while (in.hasNextInt()){

int a = in.nextInt();

int b = in.nextInt();

System.out.println(a+b);

}

Решение задачи

Пока вводятся пары чисел, они считываются и на экран выводится их сумма.

Ссылки

Условие на e-olymp
Решение на языке C++ с описанием решения
Код на java

e-olymp 519. Сумма квадратов

09/12/2018 by Иван Василевский

Условие задачи
Найти сумму квадратов двух чисел.
Входные данные
Два целых числа $a$ и $b$. Числа не превышают $10^9$ по абсолютной величине.
Выходные данные
Выведите одно целое число $a^2+b^2$
Тесты

Входные данные	Выходные данные
2 2	8
5 5	50
-5 -2	29
500 500	500000
1210 1250	3026600

Код программы

import java.util.*;

public class Main
{
  public static void main(String []args)
  {
    Scanner scanner = new Scanner(System.in);
    long a = scanner.nextLong();
    long b = scanner.nextLong();
    System.out.println(a * a + b * b);
  }
}

import java.util.*;

public class Main

{

public static void main(String []args)

{

Scanner scanner = new Scanner(System.in);

long a = scanner.nextLong();

long b = scanner.nextLong();

System.out.println(a * a + b * b);

}

Решение задачи
Создаем 2 переменные a и b, в которые записываем данные, дальше выводим на экран одно целое число, которое равно $a^2+b^2$.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 1128. Проблема Лонги

02/12/2018 by Алиса Ворохта

Задача

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:
Дано целое число [latex]n[/latex] [latex](1 < n < 231)[/latex], Вы должны вычислить [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].
"О, я знаю, я знаю!" — воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.

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

Каждая строка содержит одно число [latex]n[/latex].

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

Для каждого значения [latex]n[/latex] следует вывести в отдельной строке сумму [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].

Тесты

Входные данные	Выходные данные
[latex]2[/latex] [latex]6[/latex]	$3$ $15$
[latex]1[/latex] [latex]50[/latex] [latex]100[/latex]	$1$ $195$ $520$
[latex]7[/latex] [latex]4791[/latex] [latex]12345678[/latex] [latex]478900[/latex]	$13$ $15965$ $170994915$ $4980040$
[latex]123[/latex] [latex]7777[/latex] [latex]157423949[/latex] [latex]904573[/latex] $2147483648$	$405$ $54873$ $613124817$ $1809145$ $35433480192$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long n, gcd, primeNumInPow, power;
		Scanner in = new Scanner(System.in);
    	while(in.hasNextLong()){
    		n = in.nextLong();
        	gcd = 1;
        	for(long i = 2; i * i <= n; i++) {
            	if(n % i == 0) {
                	power = 0; primeNumInPow = 1;
                	while(n % i == 0) {
                    	power++;
                    	primeNumInPow *= i;
                    	n /= i;
                	}
                	gcd *= (power + 1)*primeNumInPow - power*primeNumInPow/i;
            	}
        	}       
        	if (n > 1) gcd *= (2*n - 1);
        	System.out.println(gcd);
    	}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

long n, gcd, primeNumInPow, power;

Scanner in = new Scanner(System.in);

while(in.hasNextLong()){

n = in.nextLong();

gcd = 1;

for(long i = 2; i * i <= n; i++) {

if(n % i == 0) {

power = 0; primeNumInPow = 1;

while(n % i == 0) {

power++;

primeNumInPow *= i;

n /= i;

}

gcd *= (power + 1)*primeNumInPow - power*primeNumInPow/i;

}

if (n > 1) gcd *= (2*n - 1);

System.out.println(gcd);

}

Согласно свойству НОД, если некоторые числа [latex]a_1[/latex] и [latex]a_2[/latex] взаимно просты, то [latex]\gcd \left(a_1 \cdot a_2, c\right) = \gcd \left(a_1, c\right) \cdot \gcd \left(a_2, c\right)[/latex], где [latex]c[/latex] — некоторая константа. Если же вместо [latex]c[/latex] взять [latex]i[/latex] ([latex] 1 ≤ i ≤ a_1 \cdot a_2[/latex]) и просуммировать по [latex]i[/latex] обе части равенства, получим:
[latex]\sum\limits_{i=1}^{a_1 \cdot a_2} \gcd \left(a_1 \cdot a_2, i\right) = \sum\limits_{i=1}^{a_1 \cdot a_2} \left(\gcd \left(a_1, i\right) \cdot \gcd \left(a_2, i\right)\right) = \sum\limits_{i=1}^{a_1} \gcd \left(a_1, i\right) \cdot \sum\limits_{i=1}^{a_2} \gcd \left(a_2, i\right)[/latex].
Значит мы можем данное число представить как произведение простых в некоторых степенях. Эти числа, очевидно, будут взаимно простыми, из чего следует возможность применения данного свойства и последующего суммирования по [latex]i[/latex].
Теперь докажем, что для любого простого числа [latex]p[/latex] в степени [latex]a\geqslant 1[/latex] верно следующее равенство:
[latex]\sum\limits_{i=1}^{p^a} \gcd\left(p^a, i\right) = \left(a + 1\right)\cdot p^a — a \cdot p^{a-1} [/latex].
Обозначим $\sum\limits_{i=1}^{r} \gcd\left(r, i\right)$ как $g\left(r\right)$.
База индукции:
[latex]a = 1[/latex]:
$$g\left(p\right) = \gcd\left(p, 1\right) + \gcd\left(p, 2\right) + \ldots + \gcd\left(p, p\right) = \left(p — 1 \right) + p = 2 \cdot p — 1.$$
Если [latex]a = 2[/latex]:
$$g\left(p^{2}\right) = \gcd\left(p^{2}, 1\right) + \gcd\left(p^{2}, 2\right) + \ldots + \gcd\left(p^{2}, p\right) + \gcd\left(p^{2}, p + 1\right) + \ldots + \\ + \gcd\left(p^{2}, 2 \cdot p\right) + \ldots + \gcd\left(p^{2}, p^{2}\right) = 1 + 1 + \ldots + p + 1 + \ldots + p + \ldots + p^{2} = \\ = \left( p^{2} — p \right) + p \cdot \left( p — 1 \right) + p^{2} = 3 \cdot p^{2} — 2\cdot p.$$
Для любых $a \geqslant 2$:
$$g\left(p^{a}\right) = \sum\limits_{j=1}^{p^{a-1}} \gcd\left(p^a, j\right) + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a, j\right) + p^{a} =g\left(p^{a — 1}\right) + p^{a} + \\ + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right).$$
Причем:
$$\sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right) = \sum\limits_{j=1}^{p^{a} — p^{a-1} — 1} \gcd\left(p^{a — 1}, j\right) = \\ = \sum\limits_{j=1}^{p^{a} — p^{a-1}} \gcd\left(p^{a — 1}, j\right) — p^{a — 1} = \left( p — 1\right)\cdot g\left(p^{a-1}\right) — p^{a-1}.$$
Откуда следует:
$$g\left(p^{a}\right) = p^{a} — p^{a-1} + p\cdot g\left(p^{a-1}\right).$$
Предположение индукции:
Пусть [latex]a = b[/latex]:
$$g\left(p^{b}\right) = \left(b + 1\right) \cdot p^b — b \cdot p^{b-1}.$$
Шаг индукции:
Пусть [latex]a = b + 1[/latex]:
$$g\left(p^{b + 1}\right) = p^{b + 1} — p^{b} + p\cdot g\left(p^{b}\right) = p^{b + 1} — p^{b} + p\cdot \left[\left(b+1\right) \cdot p^{b} + b\cdot p^{b-1}\right] = \\ = \left(b + 2\right)\cdot p^{b+1} — \left(b + 1\right)\cdot p^{b}.$$

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 542. Поставка содовой воды

23/09/2018 by Карина Миловская

Задача

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

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

Три целых неотрицательных числа $e$, $f$, $c$, где $e$ $\left(e < 1000\right)$ — количество пустых бутылок, имеющихся у Тима в начале дня, $f$ $\left(f < 1000\right)$ — количество пустых бутылок, найденных в течение дня, и $c$ $\left(1 < c < 2000\right)$ — количество пустых бутылок, необходимых для покупки новой бутылки.

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

Сколько бутылок содовой воды смог выпить Тим, когда его замучила жажда?

Тесты

Входные данные	Выходные данные
[latex]9[/latex] [latex]0[/latex] [latex]3[/latex]	[latex]4[/latex]
[latex]5[/latex] [latex]5[/latex] [latex]2[/latex]	[latex]9[/latex]
[latex]0[/latex] [latex]8[/latex] [latex]4[/latex]	[latex]2[/latex]
[latex]22[/latex] [latex]0[/latex] [latex]4[/latex]	[latex]7[/latex]

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int e, f, c;
		Scanner in = new Scanner(System.in);
		e = in.nextInt();
		f = in.nextInt();
		c = in.nextInt();
		System.out.print((int)((e + f)/(c - 1 + 0.0001)));
		
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

int e, f, c;

Scanner in = new Scanner(System.in);

e = in.nextInt();

f = in.nextInt();

c = in.nextInt();

System.out.print((int)((e + f)/(c - 1 + 0.0001)));

}

Решение

Можно считать, что изначально у Тима имеется $e+f$ пустых бутылок. Допустим, у него есть хотя бы $c$ бутылок, необходимых для покупки новой, Тим идет и меняет их на одну полную бутылку. Затем выпивает её, после чего общее количество пустых у него уменьшается на $c — 1$. То есть за $e + f$ пустых бутылок он сможет выпить $\frac{e + f}{c — 1}$ бутылок содовой воды. Нам также следует добавить к $c — 1$ маленькую константу $a = 0.0001$, чтобы в случае, когда количество бутылок кратно $c — 1$, Тиму нельзя было взять новую бутылку с недостающим количеством пустых бутылок для этого. Следовательно, он должен выпить на одну бутылку меньше. В результате выводим целое число бутылок содовой воды, которые Тим смог выпить, когда его замучила жажда.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

Ю4.35

23/08/2017 by Валентин Лавриненко

Постановка задачи

Совместная работа. Известно время $latex t_1,t_2,\cdots,t_n$ , за которое некоторую работу может выполнить каждый из рабочих бригады, работая в одиночку. Сколько времени понадобится бригаде на выполнение этой работы, если они будут работать совместно (и при этом никто из них не «сачкует»)?

Тесты

Количество рабочих n.	Время t каждого рабочего, требуемое для выполнения некоторой работы.	Время совместной работы.
3	5 7 9	2.2
4	7 9 11 23	2.6
4	1 2 3 4	0.5
5	3 1 5 2 3	0.4

Код

import java.util.*;
import java.lang.*;
 
class Task5
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		double workingTime, sum = 0;
		for(;n>0;n--) 
		{
			workingTime=input.nextDouble();
			sum+=1/workingTime;
		}
		System.out.printf("Работа будет выполнена за%5.1f часов \n", 1/cof);
	}
}

import java.util.*;

import java.lang.*;

class Task5

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n = input.nextInt();

double workingTime, sum = 0;

for(;n>0;n--)

{

workingTime=input.nextDouble();

sum+=1/workingTime;

}

System.out.printf("Работа будет выполнена за%5.1f часов \n", 1/cof);

}

Описание решения

В данной задаче нам нужно найти время, за которое рабочих выполнят какую-то совместную работу. В задаче не указан общий объём выполняемой работы, по-этому зададим его как 1. Время совместной работы находят по формуле: $latex \frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\cdots+\frac{1}{t_n}}$ .

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

Посмотреть, как работает программа можно на сайте ideone.
Задача была решена на основе данного решения.

Условие задачи

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

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

Тесты

Программный код

Решение

Ссылки

Задача

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

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

Тесты

Решение

Задача

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

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

Тесты

Код задачи

Решение задачи

Ссылки

A + B

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

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

Тесты

Код программы

Решение задачи

Ссылки

Задача

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

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

Тесты

Код программы

Решение задачи

Ссылки

Задача

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

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

Тесты

Код программы

Решение задачи

Ссылки

2 2

8

5 5

50

-5 -2

29

500 500

500000

1210 1250

3026600

Задача

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

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

Тесты

Код программы

Ссылки

Задача

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

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

Тесты

Код программы

Решение

Ссылки

Постановка задачи

Тесты

Код

Описание решения