Длинная арифметика запрос о целых числах [Вальядолид, 424]

жүктеу/скачать 90.25 Kb.

Дата	19.07.2016
өлшемі	90.25 Kb.
	#208896

ДЛИННАЯ АРИФМЕТИКА
1. Запрос о целых числах [Вальядолид, 424]. Найти сумму нескольких длинных целых чисел.

Вход. Содержит не более 100 строк. Каждая строка содержит длинное целое число, состоящее не более чем из 100 цифр. Последняя строка содержит 0 и не обрабатывается.

Выход. Следует вывести сумму всех входных чисел.

Пример входа	Пример выхода
123456789012345678901234567890	370370367037037036703703703670
123456789012345678901234567890
123456789012345678901234567890
0

2. 500! [Вальядолид, 623]. Для каждого входного n вычислить n!.

Вход. Каждая строка содержит значение n (n  1000).

Выход. Для каждого входного n вывести две строки. Первая строка содержит значение n, за которым следует ‘!’. Вторая строка содержит значение n!.

Пример входа	Пример выхода
10	10!
30	3628800
	30!
	265252859812191058636308480000000

3. Произведение [Вальядолид, 10106]. Вычислить произведение двух длинных чисел x и y, 0  x, y  10²⁵⁰.

Вход. Каждый тест состоит из двух строк, которые содержат множители x и y.

Выход. Для каждого теста вывести в отдельной строке произведение чисел x и y.

Пример входа	Пример выхода
12	144
12	444444444444444444444444
2
222222222222222222222222

4. Я люблю большие числа! [Вальядолид, 10220]. Для заданного входного n вычислить сумму цифр его факториала.

Вход. Каждая строка содержит целое число n, n  1000.

Выход. Вывести сумму цифр числа n!.

Пример входа	Пример выхода
5	3
60	288
100	648

5. Если бы мы снова стали детьми [Вальядолид, 10494]. Необходимо найти частное или остаток от деления длинного целого числа на короткое целое.

Вход. Каждая строка содержит два числа, разделенных знаком ‘/’ (целочисленное деление) или ‘%’ (остаток от деления). Между числами и знаком операции может находиться произвольное число пробелов. Первое число m является длинным целым. Второе целое n лежит в промежутке 0 < n < 2³¹.

Выход. Для каждого теста вывести значение m / n или m % n в зависимости от операции.

Пример входа	Пример выхода
110 / 100	1
99 % 10	9
2147483647 / 2147483647	1
2147483646 % 2147483647	2147483646

6. Упрощение дробей [Вальядолид, 10814]. Написать программу, которая сокращает заданную дробь.

Вход. Первая строка содержит количество тестов n (n  20). Каждая из следующих n строк содержит дробь в виде p / q (1  p, q  10³⁰).

Выход. Для каждого теста вывести дробь после сокращения.

Пример входа	Пример выхода
4	1 / 2
1 / 2	1 / 2
2 / 4	1 / 1
3 / 3	2 / 1
4 / 2

УКАЗАНИЯ И РЕШЕНИЯ
1. Запрос о целых числах [Вальядолид, 424]. Следует воспользоваться классом BigInteger и сложить все входные числа.

Реализация. Установим длину чисел равной 110. В переменной res накапливаем сумму. Строку цифр с очередным входным числом запоминаем в массиве s и преобразовываем в длинное целое temp. Пока не встретилась строка, содержащая 0, присваиваем переменной res значение суммы res и temp.

#include

#define MAXLENGTH 110

using namespace std;

class BigInteger{ . . . };
void main(void)

{

BigInteger res("0"),temp("0");

char s[MAXLENGTH];

while(scanf("%s",s),s[0]!='0')

{

temp = BigInteger(s);

res = res + temp;

}

res.print(); printf("\n");

}
2. 500! [Вальядолид, 623]. Воспользуемся классом BigInteger. Вычислим все значения факториалов чисел от 0 до 1000. Для каждого входного n, выводим соответствующее значение n!. Предвычисление факториалов всех чисел обязательно, иначе получим Time Limit.

Реализация. Установим длину чисел MAXLENGTH равной 3000, значения факториалов будут вычисляться для всех чисел от 0 до MAXN-1. Объявим глобальный массив fact, для которого fact[i]= i!.

#include

#define MAXLENGTH 3000

#define MAXN 1001
class BigInteger{ . . . };

BigInteger fact[MAXN];

void main(void)

{

int i;

Вычисляем все значения fact[i]= i!, i = 0, …, MAXN-1. Для каждого входного i выводим значение fact[i] при помощи функции print.
fact[0] = fact[1] = BigInteger(1);

for(i=2;i

while(scanf("%d",&i) == 1)

{

printf("%d!\n",i);

fact[i].print();

}

3. Произведение [Вальядолид, 10106]. Воспользуемся классом BigInteger для выполнения длинного умножения.

Реализация. Поскольку x, y  10²⁵⁰, то произведение чисел состоит из не более чем 500 цифр. Положим длину чисел MAXLENGTH равной 501.

#include

#define MAXLENGTH 501

using namespace std;

class BigInteger{ . . .};
void main(void)

{
В основном цикле программы читаем множители и находим их произведение.

char s1[MAXLENGTH],s2[MAXLENGTH];

while(gets(s1),gets(s2))

(BigInteger(s1) * BigInteger(s2)).print();

}
4. Я люблю большие числа! [Вальядолид, 10220]. Воспользуемся классом BigInteger. Используя операцию длинного умножения, найдем факториалы всех чисел от 0 до 1000, вычислим сумму их цифр и запомним эти значения в массиве fact. Для каждого входного n будем выводить fact[n].

Реализация. Положим длину чисел MAXLENGTH равной 3000. Все значения сумм цифр чисел от 0! до (MAXN-1)! занесем в массив fact. Исходя из условия, положим MAXN=1001.

#include

#define MAXLENGTH 3000

#define MAXN 1001
class BigInteger{

. . .

int DigitSum(void)

{

int i,res = 0;

for(i=0;i

return res;

}

};

int fact[MAXN];

void main(void)

{

int i;

Положим fact[0] = fact[1] = 1, так как 0! = 1! = 1 и сумма цифр этих значений равна 1. В переменной a вычисляем все значения факториалов чисел от 2 до 1000, при помощи функции DigitSum находим их суммы цифр, которые заносим в массив fact.
BigInteger a(1);

fact[0] = fact[1] = 1;

for(i=2;i

{

a = a * i;

fact[i] = a.DigitSum();

}
Для каждого входного i выводим значение fact[i].

while(scanf("%d",&i) == 1)

printf("%d\n",fact[i]);

}
5. Если бы мы снова стали детьми [Вальядолид, 10494]. В задаче необходимо реализовать деление длинного целого числа на короткое целое. Будем реализовывать деление в столбик. Пусть следует разделить число a₁a₂…a_k на n. Пусть r₁r₂…r_l – полученное частное. Положим вначале текущий остаток ost равным нулю. Снос очередной цифры делимого эквивалентен умножению текущего остатка на 10 и прибавления к нему этой цифры. То есть после сноса цифры a_i получим 10 * ost + a_i. Частным от деления этого числа на 10 будет очередная цифра частного r_i, а остатком от его деления на 10 будет новый остаток. Эту операцию следует провести для всех цифр делимого, то есть k раз. В частном получим r₁ = … = r_t = 0, где t – максимальный номер цифры, для которой a₁…a_t < n (то есть при делении на n чисел a₁, a₁a₂, a₁…a_t в частном получается ноль). Таким образом, в случае вывода частного следует пропустить ведущие нули.

Реализация. В массиве m будем хранить делимое, в res – частное. Делитель n следует объявить как 64-битовое целое, иначе в дальнейших вычислениях будет иметь место переполнение. В переменной ost будем хранить остаток от деления m на n.

#include

#include
char c;

int i,m[1000],res[1000],k;

long long n,ost;
void main(void)

{
Пока не конец файла для каждого теста посимвольно читаем первое число (делимое) в массив m. Пропускаем пробелы, после чего в переменной c будет находиться знак операции. Читаем второе число в переменную n. Следует вместе с переменной n прочитать символ перехода на новую строку ‘\n’ (иначе при посимвольном чтении делимого со следующего теста первым прочитанным символом будет ‘\n’, а не первая цифра числа).

while (!feof(stdin))

{

k=0;

while(isdigit(c = getchar())) m[k++] = c - '0';

while((c = getchar()) == ' ');

scanf("%d\n",&n);
Положим остаток ost равным нулю. Совершаем деление m на n в столбик.
ost = 0;

for(i=0;i

{

res[i] = (int)((ost*10 + m[i]) / n);

ost = (ost*10 + m[i]) % n;

}
Если в тесте следует выполнить операцию взятия остатка, то выводим значение переменной ost. Иначе выводим частное, которое хранится в массиве res. При выводе частного необходимо пропустить ведущие нули. Отдельно следует обработать случай, когда частное равно нулю.

if (c == '%') printf("%lld\n",ost);

else

{

i=0; while((res[i]==0) && (i < k)) i++;

if (i < k) for(;i

else printf("0");

printf("\n");

}

}
6. Упрощение дробей [Вальядолид, 10814]. Поскольку входные числа не более 10³⁰, то следует использовать класс длинной арифметики BigInteger. Для сокращения дроби p / q следует найти d = НОД(p, q) и разделить числитель и знаменатель дроби на d.

Реализация. Для вычисления наибольшего общего делителя двух длинных чисел функция GCD использует константу 0, занесенную в переменную Zero.

#include

using namespace std;
class BigInteger{ . . . };

BigInteger Zero(0);

BigInteger GCD(BigInteger a, BigInteger b)

{

if (b > Zero) return GCD(b,a.mod(b));

return a;

}
void main(void)

{

int tests,i;

char s[32];

string s1,s2;

BigInteger a,b,d;
Читаем количество тестов tests. Заносим числитель и знаменатель дроби в переменные p и q типа BigInteger.
scanf("%d",&tests);

for(i=0;i

{

scanf("%s",s); a = BigInteger(string(s)); scanf("%s",s);

scanf("%s",s); b = BigInteger(string(s));

d = GCD(a,b);

a = a / d; b = b / d;

a.print();printf(" / "); b.print();printf("\n");

}

}

СПИСОК ИСПОЛЬЗОВАННЫХ ЗАДАЧ

[Вальядолид] acm.uva.es/problemset:

424 (Запрос о целых числах), 623 (500!), 10106 (Произведение), 10220 (Я люблю большие числа!), 10494 (Если бы мы снова стали детьми), 10814 (Упрощение дробей).

жүктеу/скачать 90.25 Kb.

Достарыңызбен бөлісу:

Длинная арифметика запрос о целых числах [Вальядолид, 424]

Реализация. Поскольку x, y  10250, то произведение чисел состоит из не более чем 500 цифр. Положим длину чисел MAXLENGTH равной 501.

Реализация. Положим длину чисел MAXLENGTH равной 3000. Все значения сумм цифр чисел от 0! до (MAXN-1)! занесем в массив fact. Исходя из условия, положим MAXN=1001.

Реализация. Для вычисления наибольшего общего делителя двух длинных чисел функция GCD использует константу 0, занесенную в переменную Zero.

Реализация. Поскольку x, y  10²⁵⁰, то произведение чисел состоит из не более чем 500 цифр. Положим длину чисел MAXLENGTH равной 501.