Задача про степень большого числа :)
От: OlegO Россия http://www.mediachase.ru
Дата: 10.02.03 08:53
Оценка:
Очень красивая задача (особенно ее решение):

Для всех чисел от 1 до 1000000 , найти все числа третья степень которого в конце содержит само число.


Например:

1 : 1^3 = 1 (На конце 1)
5 : 5^3 = 125 (На конце 5)
...

PS: Если кто-то вдруг знает решение, просьба немного подождать .

PS: В общем случае можно изменять степень и до какого числа считать.

PS: В идеале решается с использованием только Int32 и без каких-либо классов для работы с большими числами.
<< RSDN@Home 1.0 beta 6a >>
С уважением, OlegO.
Re: Задача про степень большого числа :)
От: Pushkin Россия www.linkbit.com
Дата: 10.02.03 09:45
Оценка:
Здравствуйте, OlegO, Вы писали:

OO>Очень красивая задача (особенно ее решение):


OO>Для всех чисел от 1 до 1000000 , найти все числа третья степень которого в конце содержит само число.

OO>

OO>PS: В идеале решается с использованием только Int32 и без каких-либо классов для работы с большими числами.

Если число N k-значное, то выражение "в конце его m-той содержится само число" означает, что

N^m = N (mod 10^k)

Так как

a*b (mod c) = a (mod c) * b (mod c)

то последовательно перемножая N надо всё время проводить деление по модулю, т.е. оставлять только последние k цифр. Поэтому больших чисел получаться не должно — максимум квадрат исходного числа.
Re: Задача про степень большого числа :)
От: WolfHound  
Дата: 10.02.03 10:12
Оценка:
Здравствуйте, OlegO, Вы писали:
Не совсем вписался в условие но я не придумал другого способа устроить умножение по модулю p*10
int maxp=1000000;
void Rec(unsigned int n, unsigned int p)
{
    if(p>=maxp)return;
    for(unsigned int i=1;i<10;i++)
    {
        unsigned int x=n+i*p;
        unsigned __int64 y=x;
        y*=x;y%=p*10;
        y*=x;y%=p*10;
        if(y%(p*10)==x)
        {
            printf("%10i\n", x);
            Rec(x, p*10);
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    Rec(0, 1);
    return 0;
}
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Задача про степень большого числа :)
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 10.02.03 10:21
Оценка:
Здравствуйте, OlegO, Вы писали:

OO>PS: Если кто-то вдруг знает решение, просьба немного подождать .


Гы! Так получится, что решив задачу, все будут молчать и писать не будут => задача не разрешима!
Но потом появится "Большой Ух" и скажет: "Всё, не могу больше терпеть! Показываюсь!"
... << RSDN@Home 1.0 beta 6 >>
Вселенная бесконечна как вширь, так и вглубь.
Re: Задача про степень большого числа :)
От: Jenyay http://jenyay.net
Дата: 10.02.03 10:45
Оценка: 8 (1)
Здравствуйте, OlegO, Вы писали:

OO>Очень красивая задача (особенно ее решение):


Полностью решить пока не получилось, но заметил, что числа надо учитывать только те, которые кончаются на 0, 1, 4, 5, 6, 9. Т.к. эти числа в кубе кончаются на самих себя. => Если большое число кончается не на них, то на самого себя его куб кончиться не может (ведь как минимум последняя цифра не совпадет).
... << RSDN@Home 1.0 beta 6 >>
Софт, исходники и фото
Re[2]: Задача про степень большого числа :)
От: Pushkin Россия www.linkbit.com
Дата: 10.02.03 11:03
Оценка:
Здравствуйте, Jenyay, Вы писали:

J>Здравствуйте, OlegO, Вы писали:


OO>>Очень красивая задача (особенно ее решение):


J>Полностью решить пока не получилось, но заметил, что числа надо учитывать только те, которые кончаются на 0, 1, 4, 5, 6, 9. Т.к. эти числа в кубе кончаются на самих себя. => Если большое число кончается не на них, то на самого себя его куб кончиться не может (ведь как минимум последняя цифра не совпадет).


А зная это, можно сделать цикл всего до 10 — перебрать вторую цифру — и получить двузначные числа с искомым свойством. И так далее — на каждый разряд всего 10 переборов!
Re: Задача про степень большого числа :)
От: Apapa Россия  
Дата: 10.02.03 12:54
Оценка: 42 (3)
Привет, OlegO!

OO>Для всех чисел от 1 до 1000000 , найти все числа третья степень которого в конце содержит само число.


Итак, если a — k-значное, то (a^3 — a) делится на 10^k, т.е. (a — 1), a или (a + 1) делится на 5^k, кроме того их произведение делится на 2^k.

Получаем по-крупному два варианта:
1) a делится на 5^k, (a — 1) или (a + 1) делится на 2^(k — 1);
2) a делится на 2^k, (a — 1) или (a + 1) делится на 5^k.

Алгоритм:
а) перебираем числа вида m * 5^k, где m от 1 до 2^k. Вместо 9*10^(k — 1) чисел перебираем всего 2^k чисел — уже не плохо! Кроме того переход к следующему числу — простая операция сложения (с 5^k разумеется).
б) в соответствиии с вариантом 1) или 2) проверяем , не делится ли соседнее число на интересующую нас степень двойки. При этом, благодаря тому, что компьютер работает с двоичными числами вторая операция осуществляется элементарно (т.е. это все-равно, что у школьника спросить делится ли 12345000 на 1000)!


Здесь могла бы быть Ваша реклама!
Re[2]: Удовлетворяет условиям
От: Apapa Россия  
Дата: 10.02.03 12:58
Оценка:
Да... Забыл написать, что решение удовлетворяеит условиям, т.к. мы даже в квадрат числа не возводим! Вообще, если мы изучаем число a, то максимум для того, чтобы определить, хорошее оно или плохое нам надо число a+1!


Здесь могла бы быть Ваша реклама!
Re[2]: Задача про степень большого числа :)
От: OlegO Россия http://www.mediachase.ru
Дата: 10.02.03 13:12
Оценка:
Здравствуйте, Real 3L0, Вы писали:

R3>Здравствуйте, OlegO, Вы писали:


OO>>PS: Если кто-то вдруг знает решение, просьба немного подождать .


R3>Гы! Так получится, что решив задачу, все будут молчать и писать не будут => задача не разрешима!

R3>Но потом появится "Большой Ух" и скажет: "Всё, не могу больше терпеть! Показываюсь!"

Конечно терпеть не надо, надо сразу говорить
<< RSDN@Home 1.0 beta 6a >>
С уважением, OlegO.
Re[3]: Удовлетворяет условиям
От: Pushkin Россия www.linkbit.com
Дата: 10.02.03 13:38
Оценка:
Здравствуйте, Apapa, Вы писали:

A>Да... Забыл написать, что решение удовлетворяеит условиям, т.к. мы даже в квадрат числа не возводим! Вообще, если мы изучаем число a, то максимум для того, чтобы определить, хорошее оно или плохое нам надо число a+1!


Хорошо, но это только для кубов...
А автор чего-то говорил про любую степень...
Re[2]: Задача про степень большого числа :)
От: OlegO Россия http://www.mediachase.ru
Дата: 10.02.03 13:52
Оценка:
Здравствуйте, WolfHound, Вы писали:

Пример не верный в частности он не находит число:

501: 501^3 = 125751501
<< RSDN@Home 1.0 beta 6a >>
С уважением, OlegO.
Re[3]: Задача про степень большого числа :)
От: WolfHound  
Дата: 10.02.03 17:01
Оценка:
Здравствуйте, OlegO, Вы писали:
Ну очепятался маленько вот исправленый и расширеный вариант
unsigned int maxp=100000000;
unsigned int pow=5;
unsigned int numBase=16;
char symbols[]="0123456789ABCDEF";
void print(unsigned int n)
{
    if(!n)
    {
        printf("\n");
        return;
    }
    print(n/numBase);
    printf("%c", symbols[n%numBase]);
}
void Rec(unsigned int n, unsigned int p)
{
    if(p>=maxp)return;
    for(unsigned int i=0;i<numBase;i++)
    {
        unsigned int x=n+i*p;
        unsigned __int64 y=x;
        for(unsigned int j=0;j<pow-1;j++)
        {
            y*=x;
            y%=p*numBase;
        }
        if(y%(p*numBase)==x)
        {
            print(x);
            Rec(x, p*numBase);
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    Rec(0, 1);
    return 0;
}

Это обьясняет повторяющеяся числа(лениво было искать противоядие)
    000000
     00000
      0000
       000
        00
         0
    000001
     00001
      0001
       001
        01
         1

хотя можно сложить в set и печатать оттуда.
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Мой вариант решения
От: OlegO Россия http://www.mediachase.ru
Дата: 11.02.03 11:05
Оценка:
Пока расскажу основную идею :

Пусть у нас есть чило N надо определить, есть ли число N на конце числа полученного N^K.

Для решения задачи вспомним про Бином Ньютона и про то, что число N можно представить в виде:

N = A*1000 + B, где A и B = [0,1000]  ;)


Тогда для N^3 мы получим:
N^3 = (A*1000 + B)^3 = (A*1000)^3 + 3*(A*1000)^2*(B) + 3*(A*1000)*(B)^2 + (B)^3 = ...


Видно, что первые два члена всегде больше 1000000 и на знаки в нижних разрадах не влияют, поэтому их просто выкидываем. Получаем более простое выражение, которое считается проще:

 ... = 3*(A*1000)*(B)^2 + (B)^3


Ну и теперь его еще можно разложить, и упростить оставляя только интересующие нас разряды, тем самым получая числа находящиеся на конце степени числа N и не превышая int32 диапозона.

Вот вобщем-то и все.
<< RSDN@Home 1.0 beta 6a >>
С уважением, OlegO.
Re: Мой вариант решения
От: Apapa Россия  
Дата: 11.02.03 11:18
Оценка: 7 (1)
Привет, OlegO!

OO>Пока расскажу основную идею :

OO>Пусть у нас есть чило N надо определить, есть ли число N на конце числа полученного N^K.
OO>N = A*1000 + B, где A и B = [0,1000]
OO>N^3 = (A*1000 + B)^3 = (A*1000)^3 + 3*(A*1000)^2*(B) + 3*(A*1000)*(B)^2 + (B)^3 = ...
OO> ... = 3*(A*1000)*(B)^2 + (B)^3
OO>Ну и теперь его еще можно разложить, и упростить оставляя только интересующие нас разряды, тем самым получая числа находящиеся на конце степени числа N и не превышая int32 диапозона.
OO>Вот вобщем-то и все.

Для третьей степени мой вариант
Автор: Apapa
Дата: 10.02.03
намного легче, быстрее и позволяет рассматривать числа вплоть до 4 294 967 294 с использованием только int32
... Этот вариант почему-то проигнорировали (наверное, из зависти... )...

Интересно было бы обощить твой вариант для произвольной степени, т.к. мой вариант на вскидку при `больших степенях не пройдет!


Здесь могла бы быть Ваша реклама!
Re[2]: Мой вариант решения
От: OlegO Россия http://www.mediachase.ru
Дата: 11.02.03 11:47
Оценка:
Здравствуйте, Apapa, Вы писали:

A>Для третьей степени мой вариант
Автор: Apapa
Дата: 10.02.03
намного легче, быстрее и позволяет рассматривать числа вплоть до 4 294 967 294 с использованием только int32
... Этот вариант почему-то проигнорировали (наверное, из зависти... )...


Да нет не из-за зависти , вариант очень хорош . Просто пока руки не дошли попробывать его в действии (реализовать) и посмотреть как он работает.

A>Интересно было бы обощить твой вариант для произвольной степени, т.к. мой вариант на вскидку при `больших степенях не пройдет!


Надо будет подумать
<< RSDN@Home 1.0 beta 6a >>
С уважением, OlegO.
Re[2]: Мой вариант решения
От: WolfHound  
Дата: 11.02.03 13:56
Оценка:
Здравствуйте, Apapa, Вы писали:

A>Для третьей степени мой вариант
Автор: Apapa
Дата: 10.02.03
намного легче, быстрее и позволяет рассматривать числа вплоть до 4 294 967 294 с использованием только int32
... Этот вариант почему-то проигнорировали (наверное, из зависти... )...


Мой вариант тоже игнорируют...хотя он для произвольной степени и для произвольной системы счисления...ну и что что перебор зато с КАКИМИ отсечениями.
unsigned int maxRec=5;
unsigned int pow=3;
unsigned int numBase=10;
char symbols[]="0123456789ABCDEF";
unsigned int nums[100];
unsigned int numsPos=0;
void Rec(unsigned int n, unsigned int p)
{
    if(numsPos>=maxRec)return;
    for(unsigned int i=0;i<numBase;i++)
    {
        unsigned int x=n+i*p;
        unsigned __int64 y=x;
        for(unsigned int j=0;j<pow-1;j++)
        {
            y*=x;
            y%=p*numBase;
        }
        if(y%(p*numBase)==x)
        {
            nums[numsPos]=i;
            for(int j=20-numsPos;j>=0;j--)    printf(" ");
            for(int j=numsPos;j>=0;j--)        printf("%c", symbols[nums[j]]);
            printf("\n");
            numsPos++;
            Rec(x, p*numBase);
            numsPos--;
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    Rec(0, 1);
    return 0;
}

unsigned __int64 использован для того чтобы умножение по модулю 2^32 под ногами не путалось.
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: Мой вариант решения
От: Apapa Россия  
Дата: 11.02.03 14:03
Оценка:
Привет, WolfHound!

WH>unsigned __int64 использован для того чтобы умножение по модулю 2^32 под ногами не путалось.




Здесь могла бы быть Ваша реклама!
Re[3]: Задача про степень большого числа :)
От: Jenyay http://jenyay.net
Дата: 11.02.03 17:04
Оценка:
Здравствуйте, Pushkin, Вы писали:

P> А зная это, можно сделать цикл всего до 10 — перебрать вторую цифру — и получить двузначные числа с искомым свойством. И так далее — на каждый разряд всего 10 переборов!


А я в этом не уверен. Во-первых, я не уверен, что это справедливо для чисел, у которых больше 1 разряда. А, во-вторых, даже если это и так, то все-равно надо проверять окончание числа с бОльшими разрядами на значение ВСЕХ пердыдущих подошедших чисел. И все-равно числа получатся слишком большие.
... << RSDN@Home 1.0 beta 6 >>
Софт, исходники и фото
Re[3]: Мой вариант решения
От: OlegO Россия http://www.mediachase.ru
Дата: 12.02.03 08:11
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Мой вариант тоже игнорируют...хотя он для произвольной степени и для произвольной системы счисления...ну и что что перебор зато с КАКИМИ отсечениями.


Ну вы еще подеритесь .
<< RSDN@Home 1.0 beta 6a >>
С уважением, OlegO.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.