| ENG RUS | Timus Online Judge |
Обсуждение задачи 1456. Джедайский ребус 2cash TO ADMIN (Problem 1456) [4] // Задача 1456. Джедайский ребус 2 25 апр 2006 19:52 I have "Time Limit" in test #4. Can you help me. [code deleted] Edited by moderator 01.06.2006 16:14 CO2 Re: TO ADMIN (Problem 1456) // Задача 1456. Джедайский ребус 2 26 апр 2006 08:17 Of course you got TLE... you algo is O(n）and certainly will get TLE svr Re: TO ADMIN (Problem 1456) [2] // Задача 1456. Джедайский ребус 2 17 авг 2007 02:25 Real Help! First of all we must diminish number of candidate to optimal. MathHelp:if (A^k)%N==1 => fi(N)%k==0 where fi(N)-Eiler function of N Try find in Internet effective algorith for fi(N). we can see that number of candidates diminished from 1000000000 to 2*sqrt(1000000000)~64000 Also if Nod(A,N)>0 print 0. Final trick is using divide recursion when calculating (A^K)%N=>O(log K)-time and don't forget use __int64 when form A*B Edited by author 17.08.2007 02:26 Denis Koshman Re: TO ADMIN (Problem 1456) // Задача 1456. Джедайский ребус 2 20 авг 2008 16:40 Good point svr! :) But number of ways diminishes to amount of divisors of phi(N) which is way less than 64000, and it's enough to factorize phi(N) itself to get them all recursively. Edited by author 20.08.2008 17:46 Semm Re: TO ADMIN (Problem 1456) // Задача 1456. Джедайский ребус 2 4 авг 2016 14:54 NOD is russian for GCD :-) Lev_Sky Some Tests // Задача 1456. Джедайский ребус 2 7 июл 2012 22:30 Give some some tests ,please Edited by author 07.07.2012 22:30 wiza WA 8 // Задача 1456. Джедайский ребус 2 11 окт 2011 13:17 Please help. What is the input? 12_liz to Admin // Задача 1456. Джедайский ребус 2 18 авг 2011 01:30 I have "Wrong answer" in test 4, but I don`t understand where my mistake.Can you help me? Please, show me test 4 or something like. Edited by author 18.08.2011 23:48 Edited by author 19.08.2011 15:36 Denis Koshman Test [2] // Задача 1456. Джедайский ребус 2 20 авг 2008 18:00 131313213 453535 Result: 14860 Cat36 Re: Test // Задача 1456. Джедайский ребус 2 25 сен 2008 16:44 by both way (O(ln n) and O(n) ) result is 112562728 Cat36 Re: Test // Задача 1456. Джедайский ребус 2 25 сен 2008 16:45 453535^14860 (131313213) !=1 !!! Barselona Help me, what algorithms against a limit time the Test ¹ 4 operates??? // Задача 1456. Джедайский ребус 2 13 апр 2007 11:27 Help me, what algorithms against a limit time the Test №4 operates??? PLEASSSSSSSSS!!!! SPIRiT Something reminded me finding a square root modulo N // Задача 1456. Джедайский ребус 2 9 июн 2006 17:27 A^X=1 mod N; if X is even, we can find quickly A^(X/2) (watch problem 1134). If X is odd, we have to solve A*A^(X-1)/2=1 mod N. Therefore we have to find inverse number for A. And so on. Well, now, it's a fast quick recursion checking two cases... Gonna check that soon...
|