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

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

10.08.2011, 19:05. Показов 4565. Ответов 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
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&amp;d=1772460536 Одним из. . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru