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

@AvengerAlive · Регистрация: 30.07.2011

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++

#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 тест. Кто может помочь?

@Dani · 11.08.2011, 19:24

Сообщение от diagon

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

Не по теме:

Аналогично, а е-олим не рекомендую там куча нюансов - за всеми не уследишь. Асмпешники тимус хвалят, как вам он?

Добавлено через 1 минуту

Не по теме:

Сообщение от diagon

Лучшие попытки рулят.

Это да. У тебя есть решение в лучших попытках?

@~~IrineK~~ · 11.08.2011, 19:27

Без учета знака:

C++

#include <iostream>
using namespace std;
 
int main()
{   int x, cur, p = 0, i;
    cout<<"X = ";
    cin>>x;
    
    for(i = 2; i<x/2+1; i++)
    {   p = 0;
        cur = x;
        while(!(cur % i)) 
        {   p++;
            cur /= i;
        }
        if(cur==1)
            break;
    }
    
    cout<<"P = ";
    if(p>1) cout<<p;
    else cout<<"1";
 
    cin.sync();cin.get();
    return 0;
}

@diagon · 11.08.2011, 19:32

Не по теме:

Сообщение от Dani

Асмпешники тимус хвалят, как вам он?

Больно много задач и рейтинга вменяемого вроде бы нету... Но то, что он интернациональный для меня плюс.

Сообщение от Dani

У тебя есть решение в лучших попытках?

Первые места:
рас
два
А так я частенько в топ попадал, правда в последнее время забил на него и приучаюсь писать нормальный код.
И вообще, где модераторы? =)
Такой оффтоп лютый стоит...

Сообщение от IrineK

Без учета знака:

В задаче же написано - знаковое число.

@~~IrineK~~ · 11.08.2011, 19:36

В задаче же написано - знаковое число.

Оставим на доработку автору поста.))

@grizlik78 · 11.08.2011, 20:11

Не по теме:

во нафлудили-то

Сообщение от Olga_

Покажите какие числа вы тестируете

Ну, над "Неверный ответ" надо подумать, а с "Исчерпан лимит времени" всё просто. Достотаточно взять большое простое число. Например 2147483647 у меня 40 секунд молотит.

@~~IrineK~~ · 11.08.2011, 20:15

2147483647 у меня 40 секунд молотит.

У меня - 20.

@grizlik78 · 11.08.2011, 20:18

Сообщение от IrineK

У меня - 20.

Ну тут сравнивать лучше в одном месте

Программа из #22 скомпилированная с теми же настройками на том же числе работает у меня 6 секунд. Всё-таки, наверное, недостаточно быстро.

@diagon · 11.08.2011, 20:23

Это убывающая геометрическая прогрессия =)

Код

real	0m9.460s
user	0m8.645s
sys	0m0.008s

P.S. функция возвращает long, а в printf написано %d... Возможно, из-за этого?

@grizlik78 · 11.08.2011, 20:47

Сообщение от diagon

P.S. функция возвращает long, а в printf написано %d... Возможно, из-за этого?

Поскольку у меня компилятор ругался (у меня long 64 бита), то я, разумеется, заменил %d на %ld
Надо попробовать наоборот, long на int заменить

Добавлено через 54 секунды
diagon, а ты про какую из 2 программ

Добавлено через 3 минуты
Хм, с интом прогамма Ольги работает 11 секунд. Я не думал, что 64-битные вычисления настолько проигрывают. Мда.

@AvengerAlive · 11.08.2011, 21:15 **[ТС]**

Люди моя реализация быстра, только 1 тест не проходит. Кто нибудь может её просто отладить?
А то что мне предлагали исчерпывают лимит времени.

@Olga_ · 11.08.2011, 21:18

Кто же думал, что вы на скорость тестируете. Вот вариант, с простыми числами тоже все вроде быстро.

C

unsigned long Nod(unsigned long n, unsigned long m)
{
    while (n && m)
        if (n >= m)
           n %= m;
        else
           m %= n;
    if (m == 0) return n;
    else return m;
}
 
long Deg(long y)
{
   unsigned long x, nod = 0, i = 2, j, k;
   x = abs(y);
   if (x == 0 || x == 1)
      return -1;
 
   while (x % i && i*i <= x)
      i++;
   if (i*i > x)
      return 1;
   x /= i;
   j = i;
   k = 1;
   while (x != 1)
   {
       if (x % i == 0)
       {
           if (i == j)
              k++;
           else
           {
              nod = Nod(k, nod);
              k = 1;
              j = i;
           }
           x /= i;
       }
       else
           if (i*i > x)
              i = x;
           else i++;
   }
   nod = Nod(k, nod);
   if (y < 0 && !(nod & 1))
      return 1;
   else
      return nod;
}
 
int main()
{
   printf("%ld\n", Deg(2147483647));
   getchar();
   return 0;
}

С числом 2147483647 моментально. Надо же оговаривать, что быстрота важна

@AvengerAlive · 11.08.2011, 21:32 **[ТС]**

Olga_, этот вариант тоже исчерпывает лимит, я же писал, где-то он зависает. Проверь что у тебя выдаёт на тесте -1024. Твой ответ 1. А мой 5. -1024 это -4 в 5ой степени. Ошибка.

@Olga_ · 11.08.2011, 21:34

Сообщение от grizlik78

Не по теме:

во нафлудили-то

Достаточно взять большое простое число. Например 2147483647 у меня 40 секунд молотит.

А как теперь?

Добавлено через 52 секунды

Сообщение от AvengerAlive

Olga_, этот вариант тоже исчерпывает лимит, я же писал, где-то он зависает

Это новый вариант, вы приглядитесь, только что написала (переделала) код

Быстрота есть, сейчас с -1024 поработаю.

@grizlik78 · 11.08.2011, 21:43

Сообщение от Olga_

Надо же оговаривать, что быстрота важна

Ну, как-бы из первого поста это можно и заметить:

Сообщение от AvengerAlive

Лимит времени: 1 секунда

Сообщение от Olga_

А как теперь?

Ну да, пока быстрым выглядит. Если ошибок нет

@AvengerAlive · 11.08.2011, 21:43 **[ТС]**

Всё! Засчитано! Тупая ошибка была! -2147483648 это отдельный случай выделить надо было, его модуля в типе Int нету. Вот она ошибочка где пряталась...

@Olga_ · 11.08.2011, 21:45

Готово:

C

unsigned long Nod(unsigned long n, unsigned long m)
{
    while (n && m)
        if (n >= m)
           n %= m;
        else
           m %= n;
    if (m == 0) return n;
    else return m;
}
 
long Deg(long y)
{
   unsigned long x, nod = 0, i = 2, j, k;
   x = abs(y);
   if (x == 0 || x == 1)
      return -1;
 
   while (x % i && i*i <= x)
      i++;
   if (i*i > x)
      return 1;
   x /= i;
   j = i;
   k = 1;
   while (x != 1)
   {
       if (x % i == 0)
       {
           if (i == j)
              k++;
           else
           {
              nod = Nod(k, nod);
              k = 1;
              j = i;
           }
           x /= i;
       }
       else
           if (i*i > x)
              i = x;
           else i++;
   }
   nod = Nod(k, nod);
   if (y < 0 && !(nod & 1))
   {
      while (nod && !(nod & 1))
         nod >>= 1;
      if (nod > 0)
         return nod;
      else
         return 1;
   }
   else
      return nod;
}
 
int main()
{
   long i;
   printf("%ld\n", Deg(-1024));
   getchar();
   return 0;
}

@AvengerAlive · 11.08.2011, 21:47 **[ТС]**

Olga_, спс, моя тоже готова)))

@Olga_ · 11.08.2011, 21:50

Сообщение от AvengerAlive

Всё! Засчитано! Тупая ошибка была! -2147483648 это отдельный случай выделить надо было, его модуля в типе Int нету. Вот она ошибочка где пряталась...

Можно и не выделять, а с 64 битами работать

C

unsigned long long Nod(unsigned long long n, unsigned long long m)
{
    while (n && m)
        if (n >= m)
           n %= m;
        else
           m %= n;
    if (m == 0) return n;
    else return m;
}
 
long Deg(long long y)
{
   unsigned long long x, nod = 0, i = 2, j, k;
   x = abs(y);
   if (x == 0 || x == 1)
      return -1;
 
   while (x % i && i*i <= x)
      i++;
   if (i*i > x)
      return 1;
   x /= i;
   j = i;
   k = 1;
   while (x != 1)
   {
       if (x % i == 0)
       {
           if (i == j)
              k++;
           else
           {
              nod = Nod(k, nod);
              k = 1;
              j = i;
           }
           x /= i;
       }
       else
           if (i*i > x)
              i = x;
           else i++;
   }
   nod = Nod(k, nod);
   if (y < 0 && !(nod & 1))
   {
      while (nod && !(nod & 1))
         nod >>= 1;
      if (nod > 0)
         return nod;
      else
         return 1;
   }
   else
      return nod;
}
 
int main()
{
   long i;
   printf("%ld\n", Deg(-2147483648));
   getchar();
   return 0;
}

Добавлено через 1 минуту

Сообщение от AvengerAlive

Olga_, спс, моя тоже готова)))

Молодец, можете мою и вашу на скорость проверить

@AvengerAlive · 11.08.2011, 21:53 **[ТС]**

Сообщение от Olga_

Можно и не выделять, а с 64 битами работать

Можно, но если писать под С, там Long long ни ни.

@Olga_ · 11.08.2011, 21:56

Сообщение от AvengerAlive

Можно, но если писать под С, там Long long ни ни.

Согласна, это гибрид. В принципе она под С++, функцию main() легко переделать, это же просто тестовый вариант

@~~IrineK~~ Заблокирован
	11.08.2011, 20:15	26
	2147483647 у меня 40 секунд молотит. У меня - 20. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	11.08.2011, 20:23	28
	Это убывающая геометрическая прогрессия =) Код real 0m9.460s user 0m8.645s sys 0m0.008s P.S. функция возвращает long, а в printf написано %d... Возможно, из-за этого? 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.08.2011, 20:47	29
	Сообщение от diagon P.S. функция возвращает long, а в printf написано %d... Возможно, из-за этого? Поскольку у меня компилятор ругался (у меня long 64 бита), то я, разумеется, заменил %d на %ld Надо попробовать наоборот, long на int заменить Добавлено через 54 секунды diagon, а ты про какую из 2 программ Добавлено через 3 минуты Хм, с интом прогамма Ольги работает 11 секунд. Я не думал, что 64-битные вычисления настолько проигрывают. Мда. 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	11.08.2011, 21:34	33
	Сообщение от grizlik78 Не по теме: во нафлудили-то Достаточно взять большое простое число. Например 2147483647 у меня 40 секунд молотит. А как теперь? Добавлено через 52 секунды Сообщение от AvengerAlive Olga_, этот вариант тоже исчерпывает лимит, я же писал, где-то он зависает Это новый вариант, вы приглядитесь, только что написала (переделала) код Быстрота есть, сейчас с -1024 поработаю. 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	11.08.2011, 21:43 [ТС]	35
	Всё! Засчитано! Тупая ошибка была! -2147483648 это отдельный случай выделить надо было, его модуля в типе Int нету. Вот она ошибочка где пряталась... 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	11.08.2011, 19:24	21
	Сообщение от diagon Не по теме: ^ аналогично =) Лучшие попытки рулят. Да и вообще своебразный такой сайт, на бейсике написан =) Правда форум там никакой... 200 задач почти набил там =) Дорешаю acmp и e-olimp покорять пойду.. Не по теме: Аналогично, а е-олим не рекомендую там куча нюансов - за всеми не уследишь. Асмпешники тимус хвалят, как вам он? Добавлено через 1 минуту Не по теме: Сообщение от diagon Лучшие попытки рулят. Это да. У тебя есть решение в лучших попытках? 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	11.08.2011, 19:32	23
	Не по теме: Сообщение от Dani Асмпешники тимус хвалят, как вам он? Больно много задач и рейтинга вменяемого вроде бы нету... Но то, что он интернациональный для меня плюс. Сообщение от Dani У тебя есть решение в лучших попытках? Первые места: рас два А так я частенько в топ попадал, правда в последнее время забил на него и приучаюсь писать нормальный код. И вообще, где модераторы? =) Такой оффтоп лютый стоит... Сообщение от IrineK Без учета знака: В задаче же написано - знаковое число. 0

@~~IrineK~~ Заблокирован
	11.08.2011, 19:36	24
	В задаче же написано - знаковое число. Оставим на доработку автору поста.)) 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.08.2011, 20:11	25
	Не по теме: во нафлудили-то Сообщение от Olga_ Покажите какие числа вы тестируете Ну, над "Неверный ответ" надо подумать, а с "Исчерпан лимит времени" всё просто. Достотаточно взять большое простое число. Например 2147483647 у меня 40 секунд молотит. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.08.2011, 20:18	27
	Сообщение от IrineK У меня - 20. Ну тут сравнивать лучше в одном месте Программа из #22 скомпилированная с теми же настройками на том же числе работает у меня 6 секунд. Всё-таки, наверное, недостаточно быстро. 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	11.08.2011, 21:15 [ТС]	30
	Люди моя реализация быстра, только 1 тест не проходит. Кто нибудь может её просто отладить? А то что мне предлагали исчерпывают лимит времени. 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	11.08.2011, 21:32 [ТС]	32
	Olga_, этот вариант тоже исчерпывает лимит, я же писал, где-то он зависает. Проверь что у тебя выдаёт на тесте -1024. Твой ответ 1. А мой 5. -1024 это -4 в 5ой степени. Ошибка. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	11.08.2011, 21:43	34
	Сообщение от Olga_ Надо же оговаривать, что быстрота важна Ну, как-бы из первого поста это можно и заметить: Сообщение от AvengerAlive Лимит времени: 1 секунда Сообщение от Olga_ А как теперь? Ну да, пока быстрым выглядит. Если ошибок нет 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	11.08.2011, 21:47 [ТС]	37
	Olga_, спс, моя тоже готова))) 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	11.08.2011, 21:53 [ТС]	39
	Сообщение от Olga_ Можно и не выделять, а с 64 битами работать Можно, но если писать под С, там Long long ни ни. 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	11.08.2011, 21:56	40
	Сообщение от AvengerAlive Можно, но если писать под С, там Long long ни ни. Согласна, это гибрид. В принципе она под С++, функцию main() легко переделать, это же просто тестовый вариант 0