С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.89/19: Рейтинг темы: голосов - 19, средняя оценка - 4.89
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257

Точная P-ая степень

10.08.2011, 19:05. Показов 4469. Ответов 41
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Точная P-ая степень
Число x является точным квадратом, если для некотого целого b, x = b2. Аналогично x является точным кубом, если для некоторого целого b, x = b3. Далее будем утверждать, что x является точной p-ой степенью, если существует такое целое b, что x = bp. По заданному целому x необходимо найти наибольшее p, для которого x является точной p-ой степенью.

Технические условия
Входные данные

Содержит одно число - 32 битовое целое знаковое x, |x| > 1.

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

Вывести наибольшее p, для которого x является точной p-ой степенью.

Лимит времени: 1 секунда
Баллы за пройденный тест: 5
Сложность: 25%

Пример
Пример входных данных
Sample 1
17

Sample 2
1073741824 Пример выходных данных
Sample 1
1

Sample 2
30

Вот моя реализация:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cmath>
#define epsilon 1e-3
using namespace std;
 
int main()
{
int i,x,t,n;
double p,k,u;
bool minus=false;
cin >> x;
if (x<0) minus=true;
x=fabs(x);
p=log(x);
n=sqrt(x)+1;
for (i=2; i<=n; i++)
{
if (x%i==0)
{
 k=log(i);
 u=p/k; t=u+epsilon;
 if (u>=t-epsilon && u<=t+epsilon) 
  {
    if (minus) 
    {
     if (t%2==1) { cout << t << endl; return 0; }
    }
   else { cout << t << endl; return 0; }
  } 
}
}
cout << 1 << endl;
return 0;
}
Не проходит 1 тест. Кто может помочь?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
10.08.2011, 19:05
Ответы с готовыми решениями:

Точная степень двойки
Написал прогу. Как сделать, чтобы при вводе числа не являющейся точной степенью двойки, прога не выводила степень? Вот задание: Дано...

Точная степень двойки
Само задание: Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае. ...

Точная замена ссылки
есть такая проблема есть сыдка в переменной $l есть html код в $buf заменяю все слки равные $l в $buf вот так Код: $buf=str_replace...

41
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
10.08.2011, 20:40
Странный у вас алгоритм какой-то... Все проще, красивее и элегантнее на самом деле. Разложите исходное число на простые множители: x=p1^{k1}...pn^{kn}, где p1<...<pn - простые числа, k1,...,kn - их степени. Тогда ответ на вашу задачу - минимальное значение из чисел k1,...,kn. А ваши логарифмы все портят, точность теряется и многое другое.

Добавлено через 26 минут
Вот функция, вычисляющая наибольшую точную степень числа x


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <limits.h>
 
long Deg(unsigned long x)
{
   long min, i = 2, j, k;
   if (x == 0 || x == 1)
      return -1;
   min = INT_MAX;
   while (x % i != 0)
       i++;
   x /= i;
   j = i;
   k = 1;
   while (x != 1)
   {
      while (x % i != 0)
          i++;
      if (i == j)
         k++;
      else
      {
          if (k < min)
             min = k;
          k = 1;
          j = i;
      }
      x /= i;
   }
   if (k < min)
      min = k;
   return min;
}
Добавлено через 10 минут
Но задачка красивая

Добавлено через 19 минут
Да, и чтобы отрицательные числа тоже корректно обрабатывались, надо кое-что учесть, вот вариант для любых 32-битных целых чисел со знаком и без.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<limits.h>
#include<math.h>
 
long Deg(long y)
{
   long x, min, i = 2, j, k;
   x = abs(y);
   if (x == 0 || x == 1)
      return -1;
   min = INT_MAX;
   while (x % i != 0)
       i++;
   x /= i;
   j = i;
   k = 1;
   while (x != 1)
   {
      while (x % i != 0)
          i++;
      if (i == j)
         k++;
      else
      {
          if (k < min)
             min = k;
          k = 1;
          j = i;
      }
      x /= i;
   }
   if (k < min)
      min = k;
   if (!(min & 1) && y < 0)
      return 1;
   else
      return min;
}
0
101 / 101 / 27
Регистрация: 10.09.2010
Сообщений: 267
11.08.2011, 01:54
Цитата Сообщение от Olga_ Посмотреть сообщение
Тогда ответ на вашу задачу - минимальное значение из чисел k1,...,kn.
Не минимальное, а НОД всех чисел последовательности "k" .
1
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
11.08.2011, 08:21
Цитата Сообщение от Overmind024 Посмотреть сообщение
Не минимальное, а НОД всех чисел последовательности "k" .
Да, точно, вы абсолютно правы, спасибо, это я частный случай значит рассматривала.

Добавлено через 12 минут
Тогда алгоритм примет такой вид:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
unsigned long Nod(unsigned long n, unsigned long m)
{
    while (n != 0 && m != 0)
        if (n >= m)
           n %= m;
        else
           m %= n;
    if (m == 0) return n;
    else return m;
}
 
long Deg(long y)
{
   long x, nod, i = 2, j, k;
   x = abs(y);
   if (x == 0 || x == 1)
      return -1;
   while (x % i != 0)
       i++;
   x /= i;
   j = i;
   nod = 0;
   k = 1;
   while (x != 1)
   {
      while (x % i != 0)
          i++;
      if (i == j)
         k++;
      else
      {
          nod = Nod(nod, k);
          k = 1;
          j = i;
      }
      x /= i;
   }
   nod = Nod(nod, k);
   if (!(nod & 1) && y < 0)
      return 1;
   else
      return nod;
}
 
int main()
{
   printf("%d\n", Deg(1073741824));
   return 0;
}
1
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 17:12  [ТС]
Olga_, вот результаты этой реализации:
1. Засчитано
2. Засчитано
3. Засчитано
4. Засчитано
5. Засчитано
6. Засчитано
7. Засчитано
8. Исчерпан лимит времени
9. Засчитано
10. Засчитано
11. Засчитано
12. Неверный ответ
13. Засчитано
14. Неверный ответ
15. Засчитано
16. Засчитано
17. Засчитано
18. Исчерпан лимит времени
19. Засчитано
20. Засчитано

И что можно сделать?
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
11.08.2011, 18:27
Цитата Сообщение от AvengerAlive Посмотреть сообщение
И что можно сделать?
Покажите какие числа вы тестируете
0
11.08.2011, 18:32

Не по теме:

полагаю, что тестирует некая онлайн-систeма типа "Школла программистов". Там числа в тестах не показывают...

0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
11.08.2011, 18:47
Цитата Сообщение от soon Посмотреть сообщение

Не по теме:

полагаю, что тестирует некая онлайн-систeма типа "Школла программистов". Там числа в тестах не показывают...

В моем алгоритме все учитывается. Я рассматриваю не модули, а числа со знаком. Например, число -4. Его максимальная степень - единица. Но если система тестирует модули, то ответ будет 2. Так что нужно уточнение задачи.
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
11.08.2011, 18:50
Цитата Сообщение от Olga_ Посмотреть сообщение
Не по теме:
полагаю, что тестирует некая онлайн-систeма типа "Школла программистов". Там числа в тестах не показывают...
e-olimp.com - по формату задачи видно ))
0
 Аватар для soon
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
11.08.2011, 18:51
Я не про это
Я имел ввиду, что входные данные не показываются пользователю
0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
11.08.2011, 18:52
Olga_, вот http://www.e-olimp.com/problems/1208
0
 Аватар для soon
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
11.08.2011, 18:52
Цитата Сообщение от Dani Посмотреть сообщение
e-olimp.com

Не по теме:

о да. Они не дали мне решить задачу №2 через std::string. И через преобразование в char. Мне лень считать количество цифр в числе, и я ушел оттуда.

0
1406 / 648 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
11.08.2011, 18:54
Цитата Сообщение от soon Посмотреть сообщение
Я не про это
Я имел ввиду, что входные данные не показываются пользователю
На ацмп такое будет: заплатишь денег - решение и тесты покажут

Добавлено через 1 минуту
Цитата Сообщение от soon Посмотреть сообщение
о да. Они не дали мне решить задачу №2 через std::string. И через преобразование в char. Мне лень считать количество цифр в числе, и я ушел оттуда.
e-olimp мне тоже не понравился... Хоть там можно через файлы задачи решать
0
11.08.2011, 18:54

Не по теме:

деньги из воздуха :D

0
11.08.2011, 18:56

Не по теме:

На этом и построен бизнес :)

0
11.08.2011, 18:58

Не по теме:

я там нашел "Образец решения на с/c++

C++
1
2
3
4
5
6
7
8
9
10
// C++ iostream
#include"iostream.h"
 
int main(){
       int a = 0, b = 0;
       cin >> a;
       cout << a/10 << " " << a%10 <<"\n";
       return 0;
 
} // main
ужаснулся. думал что с std:: заблочит решение. Однако нет, пропустили.

0
11.08.2011, 19:02

Не по теме:

На паскале там гораздо проще писать... Я плюнул и решаю на ацмп :)

1
11.08.2011, 19:06

Не по теме:

^ аналогично

0
11.08.2011, 19:15

Не по теме:

^ аналогично =)
Лучшие попытки рулят.
Да и вообще своебразный такой сайт, на бейсике написан =) Правда форум там никакой...
200 задач почти набил там =)
Дорешаю acmp и e-olimp покорять пойду...

0
11.08.2011, 19:19

Не по теме:

не советую... хотя это просто мое мнение. но вот 2 кода

C++
1
2
3
4
5
6
7
8
9
10
//my
#include <iostream>
 
int main()
{
   short a;
   std::cin >> a;
   std::cout << a / 10 << ' ' << a % 10;
   return 0;
}
и
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
 
int main()
{
   short a;
   std::cin >> a;
   std::cout << a / 10 << ' ' << a % 10 << '\n';
   return 0;
}
различия - только в '\n'. Но первый не работает, а второй проходит все тесты.

1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
11.08.2011, 19:19
Помогаю со студенческими работами здесь

Точная аппроксимация полиномом
Подскажите пожалуйста, как аппроксимировать экспериментальные данные полиномом, чтобы он проходил через все точки. При этом стоит задача...

Точная проверка ПО на ошибки
Привет. Если я memtestom(последняя версия скачаная с сайта) проверил память, было 3 прогона, и никаких ошибок не было выявлено в...

Flex точная ширина
есть структура типа: &lt;div&gt; &lt;div class = &quot;1&quot;&gt;&lt;/div&gt; &lt;div class = &quot;2&quot;&gt;&lt;/div&gt; &lt;/div&gt; нужно чтобы div class 2 был вширину 10px, а...

Точная копия DataSet
Есть такая задача, мне нужна полная копия структуры DataSet. Есть TADODataSet соединенный с базой данных, в нем определенное...

Точная настройка ОС Android
Здравствуйте. Передо мной стоит задача оптимизировать работу ОС Android и отключить всё лишнее. Подскажите каким методом это лучше всего...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru