5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
1

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

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

Author24 — интернет-сервис помощи студентам
Точная 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.08.2011, 19:05
Ответы с готовыми решениями:

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

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

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

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

41
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
10.08.2011, 20:40 2
Странный у вас алгоритм какой-то... Все проще, красивее и элегантнее на самом деле. Разложите исходное число на простые множители: 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 3
Цитата Сообщение от Olga_ Посмотреть сообщение
Тогда ответ на вашу задачу - минимальное значение из чисел k1,...,kn.
Не минимальное, а НОД всех чисел последовательности "k" .
1
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
11.08.2011, 08:21 4
Цитата Сообщение от 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  [ТС] 5
Olga_, вот результаты этой реализации:
1. Засчитано
2. Засчитано
3. Засчитано
4. Засчитано
5. Засчитано
6. Засчитано
7. Засчитано
8. Исчерпан лимит времени
9. Засчитано
10. Засчитано
11. Засчитано
12. Неверный ответ
13. Засчитано
14. Неверный ответ
15. Засчитано
16. Засчитано
17. Засчитано
18. Исчерпан лимит времени
19. Засчитано
20. Засчитано

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

Не по теме:

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

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

Не по теме:

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

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

Не по теме:

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

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

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

Не по теме:

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

0
Dani
11.08.2011, 18:56
  #15

Не по теме:

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

0
soon
11.08.2011, 18:58
  #16

Не по теме:

я там нашел "Образец решения на с/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
Dani
11.08.2011, 19:02
  #17

Не по теме:

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

1
soon
11.08.2011, 19:06
  #18

Не по теме:

^ аналогично

0
diagon
11.08.2011, 19:15
  #19

Не по теме:

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

0
soon
11.08.2011, 19:19     Точная P-ая степень
  #20

Не по теме:

не советую... хотя это просто мое мнение. но вот 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
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; ...

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru