Show all threads Hide all threads Show all messages Hide all messages |
Is it possible to solve it with Discrete Logarithm? | Igor Parfenov | 1132. Square Root | 12 Sep 2022 02:15 | 1 |
I could solve it using trivial bruteforce. But I get TL, using more clever and probably expected solution. I used this: https://e-maxx.ru/algo/discrete_root (Read only first section, we don't need anything else). The slowest part here is Discrete Logarithm, which I calculate in \sqrt{n} * log_from_map. |
We can use O(n*prime(n)) to AC this problem.It's the most easy algorithms. | Зане | 1132. Square Root | 17 Nov 2019 23:08 | 2 |
We can qsort(n) and enumeration to solve it. Notice that n is a prime.There are 2500 primes under 32767. Enumeration can solve this problem. And every ask have mostly 2 answers.最多2个解 There are 3512 primes under 32767. |
Note: a can be greater than n | Otrebus | 1132. Square Root | 17 Jul 2016 23:41 | 1 |
|
WA#2 | LNCP | 1132. Square Root | 8 Feb 2015 09:54 | 2 |
WA#2 LNCP 8 Feb 2015 09:50 I use Tonelli-Shanks algo,but i got WA#2.By now I had read all te topic but hadn't found the error.Please give me some hints or cases. the key code: int inverse(int a, int m)//thr inverse element of a(modulo m); int quickpower(int a, int n, int m)//a^n(modulo m); void sqrt(int a, int p) { if(p==2) { cout << 1 << endl; return; } if(quickpower(a,(p-1)/2,p)!=1) { cout << "No root" << endl; return; } int s, t = 0, b = 0, i, j, x, y, inv, N; for (s = p - 1; !(s & 1); s /= 2) t++; inv = inverse(a, p); x = quickpower(a, (s + 1) / 2, p); for (N = 2; quickpower(N, (p - 1) / 2, p) == 1; N++); for (i = t - 2; i >= 0; i--) { b = b ? b*b%p : quickpower(N, s, p); y = x*x%p*inv%p; for (j = 1; j <= i; j++) y = y*y%p; if (y != 1) (x *= b) /= p; } if (2 * x < p) cout << x << " " << p - x << endl; else cout << p - x << " " << x << endl; return; } I had got AC now.Really a small mistake! |
To ADMIN: problem statement is imprecise | ucs6 | 1132. Square Root | 10 Mar 2014 17:59 | 3 |
The problem states that the root should be in the range of (0, n - 1), which looks like saying 0 < x < n - 1. However apparently x can be equal to n - 1! I spent several hours stuck on WA 2 just because of this. Please change it to [0, n - 1] or whatever is precise. Could you please next test case in statement? 9 7 (ans is same as for 2 7, for people to understand that a can be greater than n) Because it's not precise and personally I spent 2-3 hours just to add (%n) stuff. |
it is very nice Problem | Adham (TUIT) | 1132. Square Root | 12 Jan 2014 14:21 | 1 |
i try so much ... in the beginning but i haven't got ACCEPTED ... But now I have got accepted. i use in the beginning a %= n. after my program is accepted. Edited by author 12.01.2014 15:15 |
if got ac it would be a great solution(must be<0.2sec)but i am frustrated with wa 2. | muhammad | 1132. Square Root | 3 Dec 2012 19:16 | 5 |
i think there must be some stupid mistake.My all tests pass it. please provide me good tests or please,kindly let me know the problem in the code: [code deleted] AC at last(.187 sec 121 kb) very very stupid mistake. if(x==n-x) just print x not x and n-x :P Edited by author 12.07.2010 10:41 Edited by author 13.07.2010 18:43 if(x==n-x) It's possible only if n==2 is it possible to happen x == n-x ??? if yes, then 2*x = n; but n is prime and is not divisible by 2. |
WA2 | Adela Neacsu | 1132. Square Root | 22 Mar 2012 00:54 | 2 |
WA2 Adela Neacsu 16 Jan 2012 19:42 I keep getting WA2, even though I read all the topics and followed all your advices. I use Tonelli-Shanks algo, which seems to work fine on my test cases, but... If anyone had WA2 and managed to solve it, please tell me, might be something simillar. Thanks in advance :) Re: WA2 monyura[ONU 1 2/3] 22 Mar 2012 00:54 |
No subject | ONU_1785 | 1132. Square Root | 21 Jan 2012 05:46 | 1 |
Edited by author 31.01.2012 21:26 |
A little help from author | Michael Medvedev (KNU training center) | 1132. Square Root | 27 Oct 2011 06:05 | 19 |
The solution is really hard enough - you must know the serious number theory :-) :-) :-) read a book Handbook of applied cryptography at http://cacr.math.uwaterloo.ca/hac/ Especcialy chapter 2 - mathematical background, and the solution to the problem is written in chapter 3 - subchapter about square root problem. Author I've read the pdf files, then write the program as the algorithm described in the file, and also "Time Limit Exceeded"! What must I pay attention for? > I've read the pdf files, then write the program as the > algorithm described in the file, and also "Time Limit > Exceeded"! > What must I pay attention for? 1. Power opreration x^n - O(log n) 2. Evaluate Legandre symbol based NOT on factorization, but in chapter 2 exist recursive algorithm (I havn't just the chapter, but I'll try to see and will tell the page) If some questions will arise, will try to answer. By the way, you can post me your solution to medv@rambler.ru and I will tell you the error (why time limit exceeded). Medvedev Michael > 2. Evaluate Legandre symbol based NOT on factorization, but > in chapter 2 exist recursive algorithm (I havn't just the > chapter, but I'll try to see and will tell the page) Hmm, Legandre for 2 numbers = 1 or -1 (-1 ~ n-1), right? If that is so, can i use Euler criteria? a^((n-1)/2)=(a/p) mod p where (a/p) - Legandre symbol. why don't you read the document posted by the author? The Important Hint: Use longint to calculate.Because it use O((logn)^3) bit-operations.Another one,you may use Euler criteria to calulate Legendre. The problem is really hard enough, but the test data is really easy enough. so the The solution is NOT really hard enough > > The problem is really hard enough, > but the test data is really easy enough. > so the The solution is NOT really hard enough > > Hello, free! What is your solution, send me please it to medv@rambler.ru I can for it send you my tests. You'll see that the tests are big and good enough. Author You know, I've realized algorithm "Zessenhaus-Kantor", but it writes Time-limit!!! This algorithm has O(log n). What is your algorithm? The solution is really hard enough - you must know the serious number theory :-) :-) :-) Simple deterministic method with complexity O(sqrt(N)) is described in "The Art Of Computer Programming" (exercise 5.25). It's just enough - my program accepted in 0.890 sec. (exercise 5.25)? I can't find it. Can you tell me at which volumn and page(although the verson may be different)? I am so interested in using search method to solve this problem... chapter 5 (without subindexes) - sorting, exercise 25, the last one before chapter 5.1 The link is broken now... Hi, I used the algorithm that is in the book you said, but I got TLE, can you help me? Do you speak about 3.34 algorithm from HAC book? How do you find quadratic non-residue modulo p? I didn't search it randomly and use precompiled array of pairs (prime, some_non-residue (mod p)). |
To those who want to solve the problem without using too much math knowledge | gojiajunchao | 1132. Square Root | 25 Oct 2011 02:25 | 3 |
First of all, K is large but the range of n is small (<=32767 and is prime); So we can process the query with same n at the same time. And use brute-force method; Note if there are solutions there are exacly two solutions. x and n-x ((n-x)^2=x^2(mod n)); Can you explain me that better, I don't understand your idea. |
If you use Shanks–Tonelli algo | sklyack | 1132. Square Root | 15 Apr 2011 22:12 | 1 |
According to this algo, we need to find b -- any quadratic non_residue modulo n, such 1<=b<=n-1. In my first programs I wrote do { b=rand()%n; }while(legendre(b, n)==1); , so, in this case 0<=b<=n-1, and all they sometimes printed right answers, sometimes -- wrong, on identical tests. Be careful with it, I spent a lot of hours to find this very stupid mistake. Right finding b is do { b=1+rand()%(n-1); }while(legendre(b, n)==1); Edited by author 15.04.2011 22:18 Edited by author 15.04.2011 22:19 Edited by author 15.04.2011 22:19 |
TLE 2 [Tips] | Stefan Marinov | 1132. Square Root | 29 Apr 2009 05:45 | 1 |
Read the other topics carefully. Everything you need is said there. Edited by author 01.05.2009 00:13 |
Can't even understand | Varun Sharma | 1132. Square Root | 21 Apr 2009 00:45 | 2 |
Hi, For input 4 17, how come the output is 2 15 ? We have to do this right ? sqrt(4 % 0) = undefined sqrt(4 % 1) = 0 sqrt(4 % 2) = 0 sqrt(4 % 3) = 1 sqrt(4 % 4) = 0 sqrt(4 % 5) = 2 sqrt(4 % 6) = 2 sqrt(4 % 7) = 2 sqrt(4 % 8) = 2 sqrt(4 % 9) = 2 sqrt(4 % 10) = 2 .. .. sqrt(4 % 16) = 2 So where is 2 15 coming from ? Is there something wrong with the problem ? Edited by author 20.04.2009 03:46 Edited by author 20.04.2009 03:46 No subject Oleg Strekalovsky [Vologda SPU] 21 Apr 2009 00:45 Edited by author 21.04.2009 00:47 Edited by author 21.04.2009 00:47 |
Same code - different results! | Ostap Korkuna (Lviv NU) | 1132. Square Root | 22 Feb 2009 21:38 | 1 |
After the rejudge my previously accepted solution got TL. Today I logged in to the site, copy-pasted my old solution (from the site), submitted it and... surprisingly got AC! Admins, don't you think it's strange? And the time my program worked is 0.39 - far from TL... Here are the ID's of my submits: 1526885 - TL 2460193 - AC |
Weak Tests!! | данные | 1132. Square Root | 11 Jan 2009 12:36 | 4 |
Ah! I think I will get an TLE but got AC the First Time! You can use brute-force for n=8k+1 and use simple math method for other cases! Edited by author 22.12.2008 20:46 Edited by author 22.12.2008 20:46 Publish worst case for your solution please. Is it when k=100000, n is always 8k+1, prime near 32767? And how much time your program work on this test on Timus check server? You may estimate it by comparing time of your current program and the same program also calculating answers (without output) for 1000/10000 such n. Edited by author 11.01.2009 12:38 |
what's the mathematical method? | Li, Yi | 1132. Square Root | 8 Dec 2008 10:44 | 7 |
I have solution which take 1.001 sec for work... It's - retrieval =)... But - i can't make it faster... =(... Use Tonelli algo for root(a,p) with precalculations for all primes in [1..33000] and you will be first as I. I don't say about evedent: basic number algos as pow(a,n,p),inv(a,p) must be effectively implemented. Also: there is simple Tonelli pseudocodes without algebraic proves. sorry iii 4 Nov 2001 19:36 sorry iii 4 Nov 2001 19:38 I wrote program that work 1.001 sec, but i can't make it faster. It's retrieval (searching) > I wrote program that work 1.001 sec, but i can't make it > faster. > It's retrieval (searching) You program have not work just 1.001 sec. The test system stopped your program when it had been runned more than 1 sec. Thanx - i didn't know it =) |
Problem 1132 "Square Root" has been rejudged (+) | Sandro (USU) | 1132. Square Root | 19 Oct 2008 11:41 | 3 |
Old tests were rather weak so we have removed them and made new test set. Now the 1st test is a test from problem statement. All submits were rejudged, about 75% AC submits got WA and TL. Thanks to Vedernikoff Sergey for help. 1. As I've understood, my old solution don't pass new tests only because there are pairs <a, n> : a >= n. 2. Brute force still gets AC in ~0.6 sec. I can say more: brute works near 0.35 seconds, my earlier solution gets TL because I love symbol "%" very much :D |
Good problem | Levenets (ONPU) | 1132. Square Root | 13 Oct 2008 17:48 | 3 |
some hints if a == 1 output 1 n - 1; in the begin a %= n; this realy helps me with WA 2 Edited by author 26.08.2008 14:42 Don't understand... if for example, a=1, n=32 the result should be 1 15 17 31... not only 1 and 31 |
2 ADMINS: WEAK TESTS!!! | Vedernikoff Sergey | 1132. Square Root | 5 Jun 2008 14:20 | 2 |
My definitely incorrect prog got AC! Where to send new tests? timus_support (at) acm.timus.ru |