Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.60
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
#1

Задача о марсианских факториалах - C++

11.03.2009, 18:28. Просмотров 2631. Ответов 8
Метки нет (Все метки)

HEEEELLP!!!!!
В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце – это конечно же нули – ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчива ются на нули начиная с 5! = 1·2·3·4·5 = 120. А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 – так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N! = 1·2·3·…·(N-1)·N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

Входные данные
Входной файл INPUT.TXT содержит числа N и K, разделенные пробелом. (1<=N<=109, 2<=K<=1000).

Выходные данные
Выведите в выходной файл OUTPUT.TXT число X - количество нулей в конце записи числа N! в системе счисления с основанием K.

примеры:

1.
input.txt:
5 10
output.txt:
1

2.
input.txt:
100 10
output.txt:
24

3.
input.txt:
100 6
output.txt:
48

4.
input.txt:
3 10
output.txt:
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2009, 18:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача о марсианских факториалах (C++):

Задача: В некотором государстве ввели компьютерный паспорт гражданина.(задача) - Pascal
Доброго времени суток,форумчане. Хотелось бы попросить помощи в решении одной задачи от умных голов. Задача: В некотором...

Задача на k-тую цифру последовательности, задача на схему Горнера. - Pascal
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности 1234567891011121314…, в которой выписаны подряд...

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника - PascalABC.NET
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

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

Задача о размещении весов по ящикам (задача о рюкзаках) - Delphi
Есть упорядоченный по невозрастанию набор весов предметов w1..wn, которые необходимо распределить по ящикам способным выдержать вес V,...

Задача линейного программирования, транспортная задача - Методы оптимизации
Всем привет. сижу на экзамене, помогите пожалуйста решить,сроно!!! заранее спасибо.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
11.03.2009, 21:12 #2
Это типа олимпиадная задача?
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
12.03.2009, 04:38  [ТС] #3
Цитата Сообщение от Humanitis Посмотреть сообщение
Это типа олимпиадная задача?
Ну можно и так сказать....
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
12.03.2009, 07:03 #4
Подсказка: задача разбивается на 2:
1) найти основание K в виде произведения простых чисел (например: 12 = 2^2*3^1)
запомнить эти простые числа и степени при них
2) для каждого числа от 2 до N проверить на делимость на эти простые числа (посчитать, сколько раз делятся на каждое из простых). Затем выбрать минимум из отношений суммы степеней при простых числах к значению их степеней в основании.
пример

Пусть требуется подсчитать кол-во 0 в 12! в системе счисления с основанием 12.
Имеем:
12 = 2^2 * 3^1

a = 2;
b = 1;

2:
sa = 0 + 1 = 1
sb = 0 + 0 = 0

3:
sa = 1 + 0 = 1
sb= 0 + 1 = 1

4:
sa = 1 + 2 = 3
sb = 1 + 0 = 1

5:
sa = 3
sb = 1

6:

sa = 4
sb = 2

7:

8:
sa = 7
sb = 2

9:
sa = 7
sb = 3

10:
sa = 8
sb = 3

11:
sa = 8
sb = 3

12:

sa = 10
sb = 4

min (10/2; 4/1) = 4
Итого 4 ноля.
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
12.03.2009, 07:22  [ТС] #5
Цитата Сообщение от Yurii_74 Посмотреть сообщение
пример

Пусть требуется подсчитать кол-во 0 в 12! в системе счисления с основанием 12.
Имеем:
12 = 2^2 * 3^1

a = 2;
b = 1;

2:
sa = 0 + 1 = 1
sb = 0 + 0 = 0

3:
sa = 1 + 0 = 1
sb= 0 + 1 = 1

4:
sa = 1 + 2 = 3
sb = 1 + 0 = 1

5:
sa = 3
sb = 1

6:

sa = 4
sb = 2

7:

8:
sa = 7
sb = 2

9:
sa = 7
sb = 3

10:
sa = 8
sb = 3

11:
sa = 8
sb = 3

12:

sa = 10
sb = 4

min (10/2; 4/1) = 4
Итого 4 ноля.

Я вооще не врубился на счет примера
и вот это вот
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Затем выбрать минимум из отношений суммы степеней при простых числах к значению их степеней в основании.
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
12.03.2009, 08:05 #6
Сначала мы нашли, из каких простых чисел состоит состоит основание (12):

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
p[0]=2; //простые числа
p[1]=3;
 
a[0]=2; // 2 у нас во второй степени
a[1]=1; // a 3 в первой
 
//больше делителей нет
 
sa[0]=0;
sa[1]=0;
 
for (int i = 2;i <=N;i++)
{
 tmp=i;
 for (int j=0;j<L;j++) //цикл по всем простым числам, составляющим основание, в примере L должно быть равно 2
 {
  while (!(tmp%p[j])) {tmp/=p[j]; sa[j]++;} //считаем кол-во степеней
 }
} 
 
tmp=sa[0]/a[0];
for (int i = 0; i<L;i++) tmp = min(tmp, sa[i]/p[i]);
Выбираем минимум из отношений - т. е. если степень при 2 = 100, а степень при 3 = 30, то в 12-ричн. сист. счисл. мы получим min(100/2;30/1) = 30 нулей (2*2*3 = 12 (следовательно + ноль в записи)). М. б. не очень понятно объясняю, и кто-нибудь сможет донести идею лучше.
Rise of Death
1 / 1 / 0
Регистрация: 10.03.2009
Сообщений: 24
12.03.2009, 08:17 #7
ОМГ, это зачем же давать такое условие "для детского сада", неужели нельзя все то же самое изложить коротко, ясно и без всякой ерунды с инопланетянами?
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
12.03.2009, 08:20  [ТС] #8
Цитата Сообщение от Rise of Death Посмотреть сообщение
ОМГ, это зачем же давать такое условие "для детского сада", неужели нельзя все то же самое изложить коротко, ясно и без всякой ерунды с инопланетянами?
Ну так сделай эту ерунду.!!!!
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
21.03.2009, 20:25  [ТС] #9
Прошу Вас, помогите, с задачкой она мне до понедельника нужна.....

Добавлено через 2 минуты 23 секунды
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Сначала мы нашли, из каких простых чисел состоит состоит основание (12):

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
p[0]=2; //простые числа
p[1]=3;
 
a[0]=2; // 2 у нас во второй степени
a[1]=1; // a 3 в первой
 
//больше делителей нет
 
sa[0]=0;
sa[1]=0;
 
for (int i = 2;i <=N;i++)
{
 tmp=i;
 for (int j=0;j<L;j++) //цикл по всем простым числам, составляющим основание, в примере L должно быть равно 2
 {
  while (!(tmp%p[j])) {tmp/=p[j]; sa[j]++;} //считаем кол-во степеней
 }
} 
 
tmp=sa[0]/a[0];
for (int i = 0; i<L;i++) tmp = min(tmp, sa[i]/p[i]);
Выбираем минимум из отношений - т. е. если степень при 2 = 100, а степень при 3 = 30, то в 12-ричн. сист. счисл. мы получим min(100/2;30/1) = 30 нулей (2*2*3 = 12 (следовательно + ноль в записи)). М. б. не очень понятно объясняю, и кто-нибудь сможет донести идею лучше.
Извини меня, если те не сложно сделай эту задачку...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.03.2009, 20:25
Привет! Вот еще темы с ответами:

Задача на файл и задача на создание очереди - Pascal
1 Дан символьный файл, содержащий, по крайней мере, один символ пробела. Удалить из файла все символы, предшествующие пробелу 2 ...

Задача Дам или задача Восьми - Алгоритмы
помогите найти ошибку в алгоритме. не находит ответ подозреваю ошибку в k, i, j package com.company; import java.util.Arrays;...

задача Коши и краевая задача - Matlab
Помогите кто чем может))


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
21.03.2009, 20:25
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru