С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

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

10.08.2011, 19:05. Просмотров 2070. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2011, 19:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Точная P-ая степень (C++):

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

Вычислить 10-ю степень двойки сложением, умножением и просто возведением в степень. - C++
Написать код на С++ или С# или на Java Вычислить 10-ю степень двойки 1 - сложением, умножением и просто возведением в степень.

Различные варианты инициализации указателя - в чём точная разница между ними? - C++
Немного непонятен один момент. Есть некий класс Statement (конструктор используется по умолчанию). Вот четыре различных записи...

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

Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача - C++
У покупателя есть n монет достоинством H(1),...,H(n). У продавца есть m монета достоинством B(1),...,B(1). Может ли купить покупатель вещь...

Как возвести дробное число в целую степень? К примеру 2,7 возвести в степень 2 на C++. - C++
Как возвести дробное число в целую степень? К примеру 2,7 возвести в степень 2 на C++.

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

Не по теме:

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



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

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

Быстрота есть, сейчас с -1024 поработаю.
0
grizlik78
Эксперт С++
1972 / 1465 / 122
Регистрация: 29.05.2011
Сообщений: 3,033
11.08.2011, 21:43 #34
Цитата Сообщение от Olga_ Посмотреть сообщение
Надо же оговаривать, что быстрота важна
Ну, как-бы из первого поста это можно и заметить:
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Лимит времени: 1 секунда
Цитата Сообщение от Olga_ Посмотреть сообщение
А как теперь?
Ну да, пока быстрым выглядит. Если ошибок нет
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 21:43  [ТС] #35
Всё! Засчитано! Тупая ошибка была! -2147483648 это отдельный случай выделить надо было, его модуля в типе Int нету. Вот она ошибочка где пряталась...
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 21:45 #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;
}
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 21:47  [ТС] #37
Olga_, спс, моя тоже готова)))
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 21:50 #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_, спс, моя тоже готова)))
Молодец, можете мою и вашу на скорость проверить
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 21:53  [ТС] #39
Цитата Сообщение от Olga_ Посмотреть сообщение
Можно и не выделять, а с 64 битами работать
Можно, но если писать под С, там Long long ни ни.
0
Olga_
842 / 184 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 21:56 #40
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Можно, но если писать под С, там Long long ни ни.
Согласна, это гибрид. В принципе она под С++, функцию main() легко переделать, это же просто тестовый вариант
0
IrineK
Заблокирован
11.08.2011, 22:13 #41
С решетом Эратосфена (точнее - "полурешетом"):
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
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{   int x, cur, p = 0, i,j;
    cout<<"X = ";
    cin>>x;
 
    int sqrt_x = static_cast<int>(sqrt(static_cast<double>(x))) + 1;
    vector<bool> S(sqrt_x, true);
    
    for(i = 2; i<sqrt_x; i++)
    {   if(S[i])
        {   p = 0;
            cur = x;
            while(!(cur % i)) 
            {   p++;
                cur /= i;
            }
            if(cur==1)
                break;
            else
                for (j = i*i; j < sqrt_x; j+=i)
                    S[j] = false;
        }
    }
    
    cout<<"P = ";
    if(p>1) cout<<p;
    else cout<<"1";
 
    cin.sync();cin.get();
    return 0;
}
теперь в 1с укладывается.
0
Kastaneda
11.08.2011, 22:21     Точная P-ая степень
  #42

Не по теме:

Блин, долго думал, зачем вы (все) так решение усложнили, пока пример входных/выходных данных и оригинал задания не посмотрел)) Вобщем там в условии опечатка:

Цитата Сообщение от AvengerAlive Посмотреть сообщение
По заданному целому x необходимо найти наибольшее p, для которого x является точной p-ой степенью.
Согласно условию задача решается руками на калькуляторе за 5 сек, не говоря уже о программном решении

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 22:21
Привет! Вот еще темы с ответами:

степень - C++
создать класс для вычисления числа n в степени k, перегрузить оператор * умножения. помогите перегрузить оператор, желательно с...

Степень - C++
Хочу реализовать 2 в 3 степени .. но не могу докумекать как это сделать .. Каким циклом сделать лучше ? 2*2*2=8 ВНИМАНИЕ НЕ...

Возведение в степень - C++
Вывести на экран таблицу степеней &quot;к&quot;, где те изменяются от 1 до 10,к-вещественое число.оперцию возведения вещественого числа в степень...

Степень симметрии - C++
Только прошу сделайте чем по проще. и через cin cout. Степенью симметрии натурального числа назовём количество пар его десятичных...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.