Show all threads Hide all threads Show all messages Hide all messages |
Page 2 |
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. |
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! |
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 |
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. |
No subject | ONU_1785 | 1132. Square Root | 21 Jan 2012 05:46 | 1 |
Edited by author 31.01.2012 21:26 |
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 |
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 |
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. |
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. |
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 |
Page 1 |
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 |
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 |
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 |
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 |
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. |
Please HELP!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | BAron | 1132. Square Root | 20 Nov 2007 01:21 | 3 |
Give me a few tests, please! Anybody, who had WA1 and then had AC, please help me!!!!!!!! Tests or any hints, please!!!!!!! Edited by author 24.06.2007 19:23 |
Please HELP!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! | BAron | 1132. Square Root | 16 Jun 2007 16:56 | 1 |
Give me a few tests, please! Anybody, who had WA1 and then had AC, please help me!!!!!!!! Tests or any hints, please!!!!!!! Edited by author 29.06.2007 09:00 |