Wrong answer 18. Can anybody help me, please? check if answer = 2 (Ferma-Euler theorem) Do you know what's the test 62? I noticed that all primes in factorization of N are also strong pseudoprimes to base just 2 or 3. Added some tests on that. Thanks. Well, it's strange, but my program with primality test that checks for strong pseudoprimes to base 2 and 3 still gets AC. N = 25326001 The answer is 3, my program with weak primality test answers 2. Thanks, your tests have been added. 3 authors have lost their AC. Sorry, but can you give me 97 test, please? Forecoding, i guess i can help. Email me your TL97 code. I think it will be too hard to understand my code :) I don't really need to understand it too deeply to help, but oh well, as you wish. I get tired, so I send my code. Good luck :) #include <queue> #include <iostream> #include <set> #include <cstdio> #include <algorithm> #include <string> #include <map> #include <string> #include <sstream> using namespace std; bool k(long double x) { long double t=floor((sqrt(x))); if (t*t==x) { return true; } else return false; } int main() { long double n;
scanf("%lf",&n); long long c=n; if(k(n)) { cout<<1; return 0; }
for(long int i=1;i<=sqrt(n)/2+2100000;i++) { long double q=n-i*i; if(k(q)) { printf("%d",2); return 0; } } for(long int i=sqrt(n);i>=sqrt(n)-2100000;i--) { long double q=n-i*i; if(k(q)) { printf("%d",2); return 0; } } long long q = (long long)n; for ( int i = 0; i <20; i ++) { long long d = 1; for ( int j = 0; j < i;j++) { d*=4; if ( q > n) break; } if ( d > q) break; if( (long long)q % d==0) { long long temp = q/d - 7; if ( temp %8==0) { printf("%d",4); return 0; } } } printf("%d",3); return 0; } I think you want i<=sqrt(n/2) not i<=sqrt(n)/2. Do you know what's the test 29? Edit: got the AC. Edited by author 03.07.2012 14:20 ALSO WA#29, what's the point? Use the Microsoft Visual C compiler or use the "int64_t" type with GCC. My program that used the "unsigned long long" type with GCC was getting WA 29. Exactly the same program, with the Visual C compiler got AC. After changing from "unsigned long long" to "int64_t", I got AC also with GCC. I don't understand why... Thanks in advance 1) If N==a^2, that is if N is a full square, the answer is 1 2) Try N = a^2 + b^2. Brute force, but "clever" brute force. This is the most expensive part of the algo 3) N is NOT a sum of 3 squares <=> N=(8k+7)*4^m This is a fast step, about O(log(N)) 4) Lagrange theorem states: each number may be presented as a sum of 4 squares: N = a^2 + b^2 + c^2 + d^2 So if the upper three cases fails, the answer will be 4. Nice algorithm! Thank you, melkiy. But you can find N = a^2 + b^2 without brute-force. I considered this case by facrotizing N to primes and using Ferma-Euler theorem. How to apply Ferma-Euler theorem to this problem ? No brute force. Moreover, we don't need to find the sum of squares, we need just answer. find factorization of N = L*m^2, where L is not divisible by p^2 for p is prime. if L==1 then answer = 1 if L has no prime divisors of the form 4*t+3 then answer = 2 (Fermat) if N != (8*t+7)*4^k then answer = 3 (Legendre) else answer = 4 Thank, every body. +1 Got AC. Edited by author 22.01.2013 20:14 If L has prime divisors of the form 4*t+3,the answer may be 2,too. How to explain this question? Fermat's theorem says that if N=a^2+b^2, then L hasn't prime divisors of the form 4t+3, and back. A simpler to calculate approach is just to check if the prime decomposition contains no ODD powers of primes that can be expressed as 4*t+3, in which case the answer is two. Can anyone help me ? I have WA on test 43 . Thanks for your attention . I followed the algorithm of luckysundog which is posted in this forum and solved it C# and C++. The same code in C# and C++ gives AC, but in Java it gives Time Limit Exceeded in test 45. I improved the code to run faster but now it gives TLE 54. I tested the code against worst case of 1000000000000037, which is a prime number. And execution time for this test was 138 milliseconds which is obviously less than 1000 (1 second). For prime 10000000000000061, it takes 185 milliseconds. Does anybody know what test 54 is? Did anybody solve this problem in Java? Can you please send me the solution to hazorman@gmail.com Thanks, Input 7 Output 4 Edited by author 12.10.2011 22:59 My algorithm is O(sqrt(n)). I dont know why it is TLE test 13. Any hints? Wow! It's great that there still are cool programmers that break the records of this (and not only this) site. And it's great that these records are still being broken and there are people who are eager to always make new records! :) No. If you TLE read forum for task 1073. Roma, O(sqrt(n)) is good time to find a, b : a^2 + b^2 = n My O(sqrt(n)) solution gets AC in 0.25 sec. ------------------- Sergey Kopeliovich [code deleted] ------------------- Вот это получает Roman Atangulov 1593 C++ Time limit exceeded 13 1.046 137 KB Edited by author 28.04.2009 21:22 Edited by author 29.04.2009 14:21 Is answered in vkontakte. I know O(N^0.5) algo, but I use array[N] :( Please tell me some ideas, how to solve this task without array? Thanks New problem 1593 was added to the Problem set. It has the same problem statements as in the problem 1073, but with bigger limitations. Thanks to Fyodor Menshikov for the idea and the implementation. Beautiful problem. Found smth new on number theory. Thanks to author! =))) nice problem :) I solved it, but I don't know why my solution is correct... I used brute force with some optimizations Sorry, but it was easy to challenge your solution. Try once again! Solved ;) int tmp = (long long) i*i; It was AC before new tests were added. ))))) Edited by author 07.02.2009 12:31 |
|