Форум программистов, компьютерный форум 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 тест. Кто может помочь?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
11.08.2011, 22:13     Точная P-ая степень #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с укладывается.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2011, 22:21     Точная P-ая степень
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Kastaneda
11.08.2011, 22:21     Точная P-ая степень
  #42

Не по теме:

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

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

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

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