Форум программистов, компьютерный форум 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 тест. Кто может помочь?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
10.08.2011, 20:40     Точная P-ая степень #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;
}
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
11.08.2011, 01:54     Точная P-ая степень #3
Цитата Сообщение от Olga_ Посмотреть сообщение
Тогда ответ на вашу задачу - минимальное значение из чисел k1,...,kn.
Не минимальное, а НОД всех чисел последовательности "k" .
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 08:21     Точная P-ая степень #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;
}
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
11.08.2011, 17:12  [ТС]     Точная P-ая степень #5
Olga_, вот результаты этой реализации:
1. Засчитано
2. Засчитано
3. Засчитано
4. Засчитано
5. Засчитано
6. Засчитано
7. Засчитано
8. Исчерпан лимит времени
9. Засчитано
10. Засчитано
11. Засчитано
12. Неверный ответ
13. Засчитано
14. Неверный ответ
15. Засчитано
16. Засчитано
17. Засчитано
18. Исчерпан лимит времени
19. Засчитано
20. Засчитано

И что можно сделать?
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 18:27     Точная P-ая степень #6
Цитата Сообщение от AvengerAlive Посмотреть сообщение
И что можно сделать?
Покажите какие числа вы тестируете
soon
11.08.2011, 18:32
  #7

Не по теме:

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

Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
11.08.2011, 18:47     Точная P-ая степень #8
Цитата Сообщение от soon Посмотреть сообщение

Не по теме:

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

В моем алгоритме все учитывается. Я рассматриваю не модули, а числа со знаком. Например, число -4. Его максимальная степень - единица. Но если система тестирует модули, то ответ будет 2. Так что нужно уточнение задачи.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 18:50     Точная P-ая степень #9
Цитата Сообщение от Olga_ Посмотреть сообщение
Не по теме:
полагаю, что тестирует некая онлайн-систeма типа "Школла программистов". Там числа в тестах не показывают...
e-olimp.com - по формату задачи видно ))
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
11.08.2011, 18:51     Точная P-ая степень #10
Я не про это
Я имел ввиду, что входные данные не показываются пользователю
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 18:52     Точная P-ая степень #11
Olga_, вот http://www.e-olimp.com/problems/1208
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
11.08.2011, 18:52     Точная P-ая степень #12
Цитата Сообщение от Dani Посмотреть сообщение
e-olimp.com

Не по теме:

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

Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.08.2011, 18:54     Точная P-ая степень #13
Цитата Сообщение от soon Посмотреть сообщение
Я не про это
Я имел ввиду, что входные данные не показываются пользователю
На ацмп такое будет: заплатишь денег - решение и тесты покажут

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

Не по теме:

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

Dani
11.08.2011, 18:56
  #15

Не по теме:

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

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:: заблочит решение. Однако нет, пропустили.

Dani
11.08.2011, 19:02
  #17

Не по теме:

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

soon
11.08.2011, 19:06
  #18

Не по теме:

^ аналогично

diagon
11.08.2011, 19:15
  #19

Не по теме:

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

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 19:19     Точная P-ая степень
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
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'. Но первый не работает, а второй проходит все тесты.

Yandex
Объявления
11.08.2011, 19:19     Точная P-ая степень
Ответ Создать тему
Опции темы

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