НГУ

Форумы НГУ
Текущее время: Вт фев 20, 2018 10:43 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 13 ] 
Автор Сообщение
 Заголовок сообщения: Несложная задачка
СообщениеДобавлено: Чт янв 13, 2005 12:00 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт мар 23, 2004 1:45 pm
Сообщения: 102
Откуда: Ой, а Вы не знаете, да? - Петр Алексеевич
35!=1033314796638614?929?66651337523200000000
Какие цифры должны стоять на месте вопросов?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 13, 2005 12:15 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Такие задачи надо будущим программистам на зачете давать. Чтобы они тут же, не отходя от кассы, за пять минут написали программу.

А если какое-то теоретико-числовое решение есть, то оно по любому длиннее компьютерного.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 13, 2005 12:48 pm 
Ну, вроде бы признаков делимости на 9 и 11 должно хватить...


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 14, 2005 7:56 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Вот именно. А на компе ещё длинную арифметику реализовывать придётся. А это париться не мало.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб янв 15, 2005 3:34 pm 
Не в сети
Редкий гость

Зарегистрирован: Сб сен 25, 2004 4:54 am
Сообщения: 19
Откуда: Роман Чепляка
Михаил Макаров писал(а):
Вот именно. А на компе ещё длинную арифметику реализовывать придётся. А это париться не мало.

Благо, есть достаточно библиотек и пакетов, с которыми париться не придеться. Думаю, ув. MinHerz самостоятельно факториал не высчитывал :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб янв 15, 2005 4:28 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Ага, я тоже так умею. Заходишь в Mathematica (или Maple, кому что нравится), набираешь 35!, давишь shift+enter, и ответ на экране. Я на это затратил от силы секунд 15.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс янв 16, 2005 7:37 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Кстати, если кто ещё не в курсе,

2005! =
10691896703413658203534264000728657803298237913390000511097680287153
85399817997002904639923173470892953507519075426971004707035253538779
15109433617615836242593038773968441524773119428263788627420939470178
91052010981515456237184361886217259476000653736069532687029679774021
02771381395537628439368543092206545991060088308912505578521825425990
65024026028938256727624936952020367713539424677940924395387453001536
61555813592254871489130868985783821498840863851671065665829933267158
67304587677673737163767575963909371931741142817998796765370896051668
12177714897819741080272702008241634778883649232099139287685621563960
02491051446558804271677964926085453100133381172435898219416169636793
43772294609665032764894638660479000444237623976457783103422052783356
37894510870275909920523363930882670663967717861050646643358183917280
61628649435302344810896287529532584654317990198296205835596763834977
89294021921964623794026248166406540019502908671423969364848040641018
51497438108748428957324767849307542143641517526935230583854208095593
28969165660789512421564467432737500437909878828247018923339324413006
07304819775089978283401701695416596517210336368821223121271020384221
18294004690428874914497671587650937896128405643772178205743999873157
93527690221382969045529773074924929043543889844237244191715452129919
80832969775135556394313239265360850668186166462096865913292316796395
60586139972568029300303513385251492722584280475186991212504131600361
11533879440719535451129842821225847671958449609941316041072212410220
04477747307107622836689081471710032754251130690475602305202512573493
18015635174641266230650625872280352668077692017525205141692101005780
94722153588328421967063357425196066968157573885801225896310854981969
42218939461416756557164669819570442383501956550826861886825772273836
23351131641522695779259983687059782773758331287298416632238405726875
29368222766733727041786499966600566404514039577697590883001696865223
87448208186954414272436258420976726123276422783285778950738204485499
56946626832833194202956265711574957121156763463297538190339158391270
50024524960765624460444427689674540400011249750038787775706014536507
10134901709349025279617024280439297589150753940666884956876690767224
63500346476054498216349640574571969046708671338574236328765361167020
55601489310843704587644556134967805558911980158893341614519707645374
42078028304341655856160751229335276142178976794874567274610431597563
86454011093408886503561456820257363577298338480452506035183305488249
95391722442051945791587228891135592140989746864554617697300861982098
33052972862071028489997022376399167178284261058597773342169267006491
00138569830785220199944537576641741374012078139156945177359499312171
11792797625357257433263348955656468852196900169310898432766093218457
94501426051284021714659126007030069437198112813298922531911037405470
67122588585750725878845877934764151517423186737159774313628854719383
09141568674444003334059460527885188017550694451986710029292125222853
02798903753687090747152275128391755957853387565213890032131604341162
72674814969679573758907048078873450803260801529970248565456208818782
83430918285771008060030559398264026085929824548736641962711803612152
37632623023424148775684875353620905461192263562324184418992754395145
67507864933186518061654928665809263215623985136898046770003939131265
66506088145251775471577914739129894448534878089771566055420058507675
03922723812649972598393615073878202824055911847331908999793145873449
96676964023389432439893080650668107930677263256386453154290070095414
62905016357178644297699403859285575879522027468428678092168473174925
85300133221242125413809980339607856790130755197120692604613075543672
14463956284454177632138566180743511443265456542511536605576580876569
58846746641469944111784971994221728635339389797910015542288830827279
98082758540183735448809656575809373790940744077523745293294277846952
52965051928713920786221489547748042267645469505624773042758552852379
66027704050117290408875770998788346869100150098430128727327545210639
15734631770850417731774312801332987685202708008096616924219477347893
04525993624256911926151791212458905845758929135354470697702396144927
10964139544686876730940717834073951742846587372952260474085496468951
40188222028196664672457795982002804051939045981904120799559154789212
68215728359406488097048600558716748895261042259770583258089758807827
95632102517864694487083312836661196167405005206831185711250034501814
73214751274845267031308814440424530934183329780614843579426998462127
57991704040542844652459531960341846843834294780123550867727442122642
62007187658890133030017486841407269532578463806707538863506568988968
27591847004202408819864765003872228801976599890518406018503642427737
48396657761599626523558522031183077045253385421134330980116171016945
62378459473570789912524701616152463927131524339042575895798861698204
97988084522959960135837518322347524335859270641357726852988364027962
11143279113833965383546214469413539823847436587098910269978647673656
68706204162226078743142041521049331454021474691376660316609104577759
15059557445312663311811847734155173213038591250236733677748049084320
28698144765033047630265592394332991413075831978211184920482933089042
80215133535214634491152242327851299630397484643159521325440521499023
98467756791545393541866690810413825066148279661037888530630550928468
44572706585706496000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн янв 17, 2005 12:43 am 
Не в сети
Редкий гость

Зарегистрирован: Сб сен 25, 2004 4:54 am
Сообщения: 19
Откуда: Роман Чепляка
Неужели так актуально?))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 19, 2005 4:35 pm 
Anonymous писал(а):
Ну, вроде бы признаков делимости на 9 и 11 должно хватить...

It's true and isn't true.
Let x be the 1st sign of question and y be the 2nd one. It is obvious that
x+y=a (mod 9)
and
x+y=b (mod 11)
for easily calculated a and b.
What we have to do now to determine x and y?


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 19, 2005 8:02 pm 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
Легко вычислить, что b=-1 и поэтому x+y=10. Также можно найти, что a=1, но это уже ничего нового не даёт.

Теперь можно использовать признак делимости на 17, который может быть получен из следующих сравнений:

10^{0} = 1 (mod 17),
10^{1} = 10 (mod 17),
10^{2} = 15 (mod 17),
10^{3} = 14 (mod 17),
10^{4} = 4 (mod 17),
10^{5} = 6 (mod 17),
10^{6} = 9 (mod 17),
10^{7} = 5 (mod 17),
10^{8} = 16 (mod 17),
10^{9} = 7 (mod 17),
10^{10} = 2 (mod 17),
10^{11} = 3 (mod 17),
10^{12} = 13 (mod 17),
10^{13} = 11 (mod 17),
10^{14} = 8 (mod 17),
10^{15} = 12 (mod 17),
10^{16} = 1 (mod 17).

Итак, число

1*16 + 0*5 + 3*9 + 3*6 + 3*4 + 1*14 + 4*15 + 7*10 + 9*1 + 6*12 + 6*8 + 3*11 + 8*13 + 6*3 + 1*2 + 4*7 + x*16 + 9*5 + 2*9 + 9*6 + y*4 + 6*14 + 6*15 + 6*10 + 5*1 + 1*12 + 3*8 + 3*11 + 7*13 + 5*3 + 2*2 + 3*7 + 2*16 + 0*5 + 0*9 + 0*6 + 0*4 + 0*14 + 0*15 + 0*10 + 0*1 = 16x + 4y + 1119

делится на 17, откуда получаем

16x + 4y = 3 (mod 17).

Используя полученное ранее равенство x+y=10, будем иметь

12x = 14 (mod 17).

Поскольку 2 взаимно просто с 17, то можем поделить данное сравнение на 2 и получить сравнение

6x = 7 (mod 17).

Такие сравнения, насколько я помню, учат решать на первом курсе. Но в данном случае всё совсем просто: домножив его на 3, будем иметь

18x = 21 (mod 17),

или, учитывая что 18 = 1 (mod 17) и 21 = 4 (mod 17),

x = 4 (mod 17).

Вспоминая, что x --- это цифра (т.е. 0<=x<=9), немедленно получаем x=4. Из равенства x+y=10 находим y=6.

Таким образом, окончательный ответ: x=4, y=6.

P.S. В данном случае признак делимости на 17 выглядит довольно громоздко. Возможно, выбрав простое число поудачнее (их всего-то остаётся четыре штуки: 19, 23, 29 и 31), вычисления можно сократить. Но всё равно не сильно. Так что меня сильно интересует, какое же решение подразумевал MinHerz.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 21, 2005 8:39 am 
I's sufficient to use modules 7 and 9.
PS. Sorry for english writing but russian in translite doesn't look better.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт янв 21, 2005 10:48 am 
Не в сети
Опытный автор

Зарегистрирован: Ср мар 24, 2004 4:04 pm
Сообщения: 624
Откуда: Михаил Макаров
digger писал(а):
I's sufficient to use modules 7 and 9.

Согласен! На самом деле, даже можно ещё сократить вычисления и воспользоваться модулями 7 и 11 в системе счисления с основанием 1000 (в этой системе под цифрой понимается трёхзначное число, составленное из трёх последовательных цифр). В этой системе счисления признаки деления на 7, 11 и 13 выглядят абсолютно одинакого (это следует из того, что 1001=7*11*13). Поэтому одним вычислением мы получаем сразу два сравнения:

x+100y-604 = 0 (mod 7),
x+100y-604 = 0 (mod 11).

После упрощения, получаем систему

x+2y = 2 (mod 7),
x+y = 10 (mod 11),

которая уже легко решается. Ответ, разумеется, получается тот же самый.

_________________
Я попал в окружение.
Кто там с белыми флагами?
Покупайте прощение.
А я исчезну оврагами.
(c) ДДТ.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб янв 22, 2005 7:44 am 
digger писал(а):
I's sufficient to use modules 7 and 9.

Sorry, it was laga. This consideration gives
x+2y = 2 (mod 7),
x+y = 1 (mod 9)
and we have extra solution x=0, y=1.
Indeed 7 and 11 are best modules.
Михаил Макаров писал(а):
На самом деле, даже можно ещё сократить вычисления и воспользоваться модулями 7 и 11 в системе счисления с основанием 1000 (в этой системе под цифрой понимается трёхзначное число, составленное из трёх последовательных цифр). В этой системе счисления признаки деления на 7, 11 и 13 выглядят абсолютно одинакого (это следует из того, что 1001=7*11*13). Поэтому одним вычислением мы получаем сразу два сравнения:

x+100y-604 = 0 (mod 7),
x+100y-604 = 0 (mod 11).

После упрощения, получаем систему

x+2y = 2 (mod 7),
x+y = 10 (mod 11)

I guess it is more simple to obtain this using 7 and 11 only. From x+y = 10 (mod 11) we have x+y = 10 and 10-y+2y=2 (mod 7) which imply y=6.


Вернуться к началу
  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 18


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB