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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
10.08.2011, 19:05     Точная P-ая степень #1
Точная 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 тест. Кто может помочь?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 19:24     Точная P-ая степень #21
Цитата Сообщение от diagon Посмотреть сообщение
Не по теме:
^ аналогично =)
Лучшие попытки рулят.
Да и вообще своебразный такой сайт, на бейсике написан =) Правда форум там никакой...
200 задач почти набил там =)
Дорешаю acmp и e-olimp покорять пойду..

Не по теме:

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



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

Не по теме:

Цитата Сообщение от diagon Посмотреть сообщение
Лучшие попытки рулят.
Это да. У тебя есть решение в лучших попытках?

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
11.08.2011, 19:27     Точная P-ая степень #22
Без учета знака:

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
#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
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 19:32     Точная P-ая степень #23

Не по теме:

Цитата Сообщение от Dani Посмотреть сообщение
Асмпешники тимус хвалят, как вам он?
Больно много задач и рейтинга вменяемого вроде бы нету... Но то, что он интернациональный для меня плюс.


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



Цитата Сообщение от IrineK Посмотреть сообщение
Без учета знака:
В задаче же написано - знаковое число.
IrineK
Заблокирован
11.08.2011, 19:36     Точная P-ая степень #24
В задаче же написано - знаковое число.
Оставим на доработку автору поста.))
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
11.08.2011, 20:11     Точная P-ая степень #25

Не по теме:

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


Цитата Сообщение от Olga_ Посмотреть сообщение
Покажите какие числа вы тестируете
Ну, над "Неверный ответ" надо подумать, а с "Исчерпан лимит времени" всё просто. Достотаточно взять большое простое число. Например 2147483647 у меня 40 секунд молотит.
IrineK
Заблокирован
11.08.2011, 20:15     Точная P-ая степень #26
2147483647 у меня 40 секунд молотит.
У меня - 20.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
11.08.2011, 20:18     Точная P-ая степень #27
Цитата Сообщение от IrineK Посмотреть сообщение
У меня - 20.
Ну тут сравнивать лучше в одном месте
Программа из #22 скомпилированная с теми же настройками на том же числе работает у меня 6 секунд. Всё-таки, наверное, недостаточно быстро.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.08.2011, 20:23     Точная P-ая степень #28
Это убывающая геометрическая прогрессия =)
Код
real	0m9.460s
user	0m8.645s
sys	0m0.008s
P.S. функция возвращает long, а в printf написано %d... Возможно, из-за этого?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
11.08.2011, 20:47     Точная P-ая степень #29
Цитата Сообщение от diagon Посмотреть сообщение
P.S. функция возвращает long, а в printf написано %d... Возможно, из-за этого?
Поскольку у меня компилятор ругался (у меня long 64 бита), то я, разумеется, заменил %d на %ld
Надо попробовать наоборот, long на int заменить

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

Добавлено через 3 минуты
Хм, с интом прогамма Ольги работает 11 секунд. Я не думал, что 64-битные вычисления настолько проигрывают. Мда.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 21:15  [ТС]     Точная P-ая степень #30
Люди моя реализация быстра, только 1 тест не проходит. Кто нибудь может её просто отладить?
А то что мне предлагали исчерпывают лимит времени.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 21:18     Точная P-ая степень #31
Кто же думал, что вы на скорость тестируете. Вот вариант, с простыми числами тоже все вроде быстро.

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
50
51
52
53
54
55
56
57
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
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 21:32  [ТС]     Точная P-ая степень #32
Olga_, этот вариант тоже исчерпывает лимит, я же писал, где-то он зависает. Проверь что у тебя выдаёт на тесте -1024. Твой ответ 1. А мой 5. -1024 это -4 в 5ой степени. Ошибка.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 21:34     Точная P-ая степень #33
Цитата Сообщение от grizlik78 Посмотреть сообщение

Не по теме:

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



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

Добавлено через 52 секунды
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Olga_, этот вариант тоже исчерпывает лимит, я же писал, где-то он зависает
Это новый вариант, вы приглядитесь, только что написала (переделала) код

Быстрота есть, сейчас с -1024 поработаю.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
11.08.2011, 21:43     Точная P-ая степень #34
Цитата Сообщение от Olga_ Посмотреть сообщение
Надо же оговаривать, что быстрота важна
Ну, как-бы из первого поста это можно и заметить:
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Лимит времени: 1 секунда
Цитата Сообщение от Olga_ Посмотреть сообщение
А как теперь?
Ну да, пока быстрым выглядит. Если ошибок нет
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 21:43  [ТС]     Точная P-ая степень #35
Всё! Засчитано! Тупая ошибка была! -2147483648 это отдельный случай выделить надо было, его модуля в типе Int нету. Вот она ошибочка где пряталась...
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 21:45     Точная P-ая степень #36
Готово:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 21:47  [ТС]     Точная P-ая степень #37
Olga_, спс, моя тоже готова)))
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 21:50     Точная P-ая степень #38
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Всё! Засчитано! Тупая ошибка была! -2147483648 это отдельный случай выделить надо было, его модуля в типе Int нету. Вот она ошибочка где пряталась...
Можно и не выделять, а с 64 битами работать

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 21:53  [ТС]     Точная P-ая степень #39
Цитата Сообщение от Olga_ Посмотреть сообщение
Можно и не выделять, а с 64 битами работать
Можно, но если писать под С, там Long long ни ни.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 21:56     Точная P-ая степень
Еще ссылки по теме:

C++ Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача
Взведение в степень C++
C++ Написать программу с функцией, вычисляющей целую степень дробного числа. Учесть,что степень может быть положительной, отрицательной, нулевой

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

Или воспользуйтесь поиском по форуму:
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 21:56     Точная P-ая степень #40
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Можно, но если писать под С, там Long long ни ни.
Согласна, это гибрид. В принципе она под С++, функцию main() легко переделать, это же просто тестовый вариант
Yandex
Объявления
11.08.2011, 21:56     Точная P-ая степень
Ответ Создать тему
Опции темы

Текущее время: 21:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru