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 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. 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! 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. 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 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. 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 :) Edited by author 31.01.2012 21:26 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)). 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. 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 Read the other topics carefully. Everything you need is said there. Edited by author 01.05.2009 00:13 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 Edited by author 21.04.2009 00:47 Edited by author 21.04.2009 00:47 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 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? Yes! 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 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. 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 =) 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 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 My definitely incorrect prog got AC! Where to send new tests? timus_support (at) acm.timus.ru |
|