Найти такие числа запись которых совпадает с последними цифрами записи их квадрата

@Juliann · Регистрация: 04.12.2016

Натолкните на мысль, пожалуйста!!! Программу пока не пишите, а дайте подсказки, или покажите код похожих программ. Очень прошу помочь
Дано натуральное число n. Среди чисел 1, ..., n найти такие, запись которых совпадает с последними цифрами записи их квадрата. Например, 6 ( ), 25 ( ) и т.д.

Добавлено через 47 минут
У меня есть вот какая идея, но она не работает((( Объясните почему и исправьте ошибки.
Очень прошу откликнитесь

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
int main()
{
    int n, i;
    cout << "n = ?\b";  cin >> n;
    for (i = 1; i <= n; i++)
        if (i < 100 && i=(i*i)%100) { cout << "i=" << i << "   " << (i*i) % 100<<endl; }
         if (100 <= i < 1000 && i = (i*i) % 1000) { cout << "i=" << i << "   " << (i*i) % 1000 << endl; }
          if (1000 <= i < 10000 && i = (i*i) % 10000) { cout << "i=" << i << "   " << (i*i) % 10000 << endl; }
           if (10000 <= i < 100000 && i = (i*i) % 100000) { cout << "i=" << i << "   " << (i*i) % 100000 << endl; }
            if (100000 <= i < 1000000 && i = (i*i) % 1000000) { cout << "i=" << i << "   " << (i*i) % 1000000 << endl; }
 
    system("pause");
}

@Juliann · 11.12.2016, 00:07 **[ТС]**

Понимаю, Байт, все понимаю. Я буду очень стараться стать настоящим хорошим программистом))) Буду стараться улавливать похожесть.
А завтра буду терзать сдедующую задачу или она будет терзать меня)

IGPIGP · 11.12.2016, 00:29

Не по теме:

Сообщение от Juliann

А завтра буду терзать сдедующую задачу или она будет терзать меня)

Слово "терзать" - замените на слово "любить". Будет намного легче. Хотя любовь это труд. Она бывает трудна. Ну и что? :)
Лишь бы, - не зла! :D

@_Ivana · 11.12.2016, 02:43

Эмм...

Простите, что влезаю, но вот накидал несколько строчек на волшебном языке (во-первых, потому что там длинная арифметика на борту из коробки, а во-вторых, очень уж он подходит для таких задачек

). Если не напутал - все требуемые числа до 20-значных включительно. absolute running time: 0.13 sec, cpu time: 0.02 sec :

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
import Data.List
 
good ns = all (uncurry (==)) $ zip (s $ n*n) (s n) where
    s = reverse . show
    n = read ns :: Integer
 
allGoodN 0 = [""]
allGoodN n = allGoodN (n-1) >>= \n -> filter good . map (:n) $ ['0'..'9']
 
tst ns = putStrLn $ show n ++ " -> " ++ show (n*n) where n = read ns :: Integer
 
main = mapM tst . sort . allGoodN $ 20

Haskell
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
0 -> 0
1 -> 1
5 -> 25
6 -> 36
25 -> 625
76 -> 5776
376 -> 141376
625 -> 390625
9376 -> 87909376
90625 -> 8212890625
109376 -> 11963109376
890625 -> 793212890625
2890625 -> 8355712890625
7109376 -> 50543227109376
12890625 -> 166168212890625
87109376 -> 7588043387109376
212890625 -> 45322418212890625
787109376 -> 619541169787109376
1787109376 -> 3193759921787109376
8212890625 -> 67451572418212890625
18212890625 -> 331709384918212890625
81787109376 -> 6689131260081787109376
918212890625 -> 843114912509918212890625
9918212890625 -> 98370946943759918212890625
40081787109376 -> 1606549657881340081787109376
59918212890625 -> 3590192236006259918212890625
259918212890625 -> 67557477392256259918212890625
740081787109376 -> 547721051611007740081787109376
3740081787109376 -> 13988211774267263740081787109376
6259918212890625 -> 39186576032079756259918212890625
43740081787109376 -> 1913194754743017343740081787109376
56259918212890625 -> 3165178397321142256259918212890625
256259918212890625 -> 65669145682477392256259918212890625
743740081787109376 -> 553149309256696143743740081787109376
2256259918212890625 -> 5090708818534039892256259918212890625
7743740081787109376 -> 59965510454276227407743740081787109376
92256259918212890625 -> 8511217494096854352392256259918212890625

http://rextester.com/TRSPA46137

@Ferrari F1 · 11.12.2016, 09:18

эхЪ, _Ivana, ты неисправим

IGPIGP · 11.12.2016, 10:45

Не по теме:

Сообщение от Ferrari F1

эхЪ, _Ivana, ты неисправим

Разве это плохо?
Серийный кодер, это звучит гордо. :yes:
Андрей, :handshake:

@Ferrari F1 · 11.12.2016, 10:47

IGPIGP, _Ivana == андрей ?
Если да, то тогда я совсем все перестал понимать в этай жизни

IGPIGP · 11.12.2016, 10:56

Не по теме:

Сообщение от Ferrari F1

Если да, то тогда я совсем все перестал понимать в этай жизни

Я вот не понимаю как за 130 ms это сделать. Мы можем сказать "Это не плюсы! Зачем это здесь! .... " и.т.д. и т.п. Но правильнее, - положить код и сказать "Вот так быстрее". :)

Байт · 11.12.2016, 11:14

Любопытно вот что. В посте 7 уважаемый IGPIGP, тоже привел ряд чисел. Последняя строчка
9713095681 2110507339713095681
отсутствует среди результатов уважаемого _Ivana, в посте 23

IGPIGP · 11.12.2016, 11:17

Байт,

Сообщение от Байт

отсутствует среди результатов уважаемого _Ivana, в посте 23

Не поможет, imho.
Он сейчас принесёт и то что у меня отсутствует. И время сократит. Я его знаю.

@Juliann · 11.12.2016, 12:47 **[ТС]**

Сообщение от IGPIGP

Слово "терзать" - замените на слово "любить". Будет намного легче. Хотя любовь это труд. Она бывает трудна. Ну и что?
Лишь бы, - не зла!

Хорошо, мы будем любить. Я программу, а она меня

Байт · 11.12.2016, 13:13

Сообщение от IGPIGP

Он сейчас принесёт

Ан может и не донесть!
Меня смутило, что в вашей серии это единственное число с окончанием на 1 (не считая самого первого). И в свое смущения я запомнил. А в серии _Ivana, бах - такого явления природы нет
И 9713095681² вряд ли может начинаться на "2". Скорее на "9". Очень подозреваю, что тут уже переполнение, мешающее все карты...

И тип unsigned long, придуманный специально для маскировки переполнений...

IGPIGP · 11.12.2016, 13:30

Сообщение от Байт

И 97130956812 вряд ли может начинаться на "2". Скорее на "9". Очень подозреваю, что тут уже переполнение, мешающее все карты...

Беда с этим. Вот ещё один алгоритм он гораздо быстрее (тот что на нулях в конце), но даёт тот же глюк. Прямое возведение в квадрат показывает что это число не верно (или глючит квадрат (шютка)

)
Картину чёрный квадрат прилагаю:

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
#include <iostream>
#include <ctime>
using namespace std;
 
int main(int argc, char* argv[])
{
unsigned long long  a, b, c, d;
const unsigned long long e=/*1000000000*/10000000000;
size_t begin_work,end_work;
begin_work=clock();
cout<<1<<'\t'<<1<<endl;// ))
for(a=5; a<e; a++)
{
if(a%1 && a%5 && a%6) continue;
c=a;
d=1;
while(c/=10){
d*=10;
}
d*=10;
b=a*(a-1);
if(!(b%d))cout<<a<<'\t'<<a*a<<endl;
}
end_work=clock();
cout<<"\ntime= "<<(end_work-begin_work)/1000<<endl;
cout<<endl;
system("pause");
return 0;
}

IGPIGP · 11.12.2016, 13:42

Сообщение от Juliann

Хорошо, мы будем любить. Я программу, а она меня

Вот!

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

Сообщение от Байт

для маскировки переполнений...

Тут оно в незамаскированном виде
макс значение 18 446 744 073 709 551 615 то есть грубо говоря 1,8e19
Когда a достигает 10 степени по порядку, его квадрат уже больше.

Так что чуть поменьше надо было выбрать.

@_Ivana · 12.12.2016, 03:28

Сообщение от Ferrari F1

эхЪ, _Ivana, ты неисправим

горбатого, как говорится, могила

Господа, если вы возьмете любой калькулятор с поддержкой длинной арифметики, то вы сможете убедиться, что

Haskell
1
9713095681^2 == 94344227708260853761

и конечно при расчете в С++ возникает переполнение, дающее ошибку. Поэтому и не принес (С)

ЗЫ мой алгоритм базируется на очевидном и тривиальном факте, который легко доказать математически а потом использовать. Я пока не буду его озвучивать, чтобы желающие могли додуматься до него самостоятельно

Но если припрете к стенке и не распарсите из хаскельного кота - то придется расколоться

Вообще хорошая задачка - написать функцию, возвращающую n-е такое число, например 200-е. Может создам кату на кодеварсах.

ЗЗЫ за взаимную сочетательную любовь!

Добавлено через 8 часов 36 минут
Собственно, по мотивам этой задачки - обещанная ката на кодеварсах: https://www.codewars.com/kata/... ef810001e8 Не знаю, откроется ли без регистрации.

IGPIGP · 12.12.2016, 10:49

Не по теме:

Сообщение от IGPIGP

if(a%1 && a%5 && a%6) continue;

a%1 - гениальное условие. Продукт кусочно-непрерывного мышления, imho.
Зато видно, что в этот код никто не вглядывался.
И слава богу. :D

Сообщение от _Ivana

ЗЗЫ за взаимную сочетательную любовь!

Если это тост, - я тут.
Если призыв к атаке, я тоже тут. :yes:

@Juliann · 12.12.2016, 13:35 **[ТС]**

Скажите, пожалуйста, что может привести к "зацикливанию" программы?

Байт · 12.12.2016, 13:51

Сообщение от Juliann

Скажите, пожалуйста, что может привести к "зацикливанию" программы?

Хороший вопрос! Да все, что угодно!

@_Ivana · 12.12.2016, 14:08

IGPIGP, это и тост и призыв одновременно

Я все лелею надежду, что кто-то догадается до оптимального алгоритма.

IGPIGP · 12.12.2016, 14:12

Не по теме:

Сообщение от _Ivana

это и тост и призыв одновременно

Тут главное, - правильная очерёдность! 8-)

@_Ivana · 12.12.2016, 14:20

IGPIGP, правильная очерёдность важна даже в моем алгоритме, что уж там говорить про остальное

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

Новые блоги и статьи Все статьи Все блоги /
Контроль уникальности строк в табличной части документа Maks 18.06.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ПланированиеСпецтехники" с табличной частью "НаличиеОборудования", разработанного в КА2. Задача: контроль уникальности строк в. . .	Клиент Uhbif79 18.06.2026 Здесь простой клиент для работы с сервером.	Сервер Uhbif79 18.06.2026 Выкладываю простейший сервер.	Дефенестрация kumehtar 18.06.2026 Узнал интересное слово. Дефенестрация. Это когда ты выбрасываешь кого-либо или что-либо из окна. Возьму на вооружение)))
Дихотомия добра и зла kumehtar 18.06.2026 Как Дзен-буддисты говорят о добре и зле: не нужно воевать против зла, нужно воевать против невежества. Тогда добро станет ествественным, и поэтому вечным. Но дело в том, что невежество всё время. . .	Своя Интернет-Компания iceja 18.06.2026 Я программист с экономическим образованием, пишу свой проект, это SaaS для бизнесов. Мне нужен co-founder с высшим экономическим образованием, и/ или инвестор. Сейчас проект в интенсивной разработке,. . .	24 Мат модель здравосохранения: функциональные требования к строительству пищеблока anaschu 18.06.2026 СРесурсами1: финансовый SD-контур, калькулятор функциональных требований пищеблока Сегодня разделили затраты в агенте Экономика по образцу модели НАСОСЫ, добавили расчёт ROI и построили первый. . .	23. что сделано за последнее время. anaschu 17.06.2026 • Эталон: Клиника НИИ питания РАМН, Москва — централизованный пищеблок, 225 коек, 180 пациентов • Git: репозиторий med2, ветка абсентеизм. Рабочий файл: СРесурсами1_v4. alp • Смежный проект:. . .

@Juliann 2 / 2 / 0 Регистрация: 04.12.2016 Сообщений: 41
	11.12.2016, 00:07 [ТС]
	Понимаю, Байт, все понимаю. Я буду очень стараться стать настоящим хорошим программистом))) Буду стараться улавливать похожесть. А завтра буду терзать сдедующую задачу или она будет терзать меня) 1

@Ferrari F1 807 / 534 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	11.12.2016, 09:18
	эхЪ, _Ivana, ты неисправим 0

@Ferrari F1 807 / 534 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	11.12.2016, 10:47
	IGPIGP, _Ivana == андрей ? Если да, то тогда я совсем все перестал понимать в этай жизни 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	11.12.2016, 11:14
	Любопытно вот что. В посте 7 уважаемый IGPIGP, тоже привел ряд чисел. Последняя строчка 9713095681 2110507339713095681 отсутствует среди результатов уважаемого _Ivana, в посте 23 1

@Juliann 2 / 2 / 0 Регистрация: 04.12.2016 Сообщений: 41
	12.12.2016, 13:35 [ТС]
	Скажите, пожалуйста, что может привести к "зацикливанию" программы? 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	12.12.2016, 14:08
	IGPIGP, это и тост и призыв одновременно Я все лелею надежду, что кто-то догадается до оптимального алгоритма. 1

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	12.12.2016, 14:20
	IGPIGP, правильная очерёдность важна даже в моем алгоритме, что уж там говорить про остальное Но я думал, что все выпили еще вчера, а сегодня пора переходить к следующему этапу. Могу дать жиииирную подсказку 0