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

@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, правильная очерёдность важна даже в моем алгоритме, что уж там говорить про остальное

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

Новые блоги и статьи Все статьи Все блоги /
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .

@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