Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
WA18 | Ilya Konik | 1593. Квадратная страна. Версия 2 | 25 янв 2021 17:40 | 1 |
WA18 Ilya Konik 25 янв 2021 17:40 Wrong answer 18. Can anybody help me, please? |
WA 62 hint | UstinovG`~ | 1593. Квадратная страна. Версия 2 | 21 июл 2020 21:42 | 1 |
check if answer = 2 (Ferma-Euler theorem) |
WA62 | ura | 1593. Квадратная страна. Версия 2 | 19 авг 2018 02:00 | 1 |
WA62 ura 19 авг 2018 02:00 Do you know what's the test 62? |
Weak tests? | Forecoding | 1593. Квадратная страна. Версия 2 | 3 июл 2016 01:34 | 10 |
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 :) |
WA 32. Why? | Yagudin Ruslan | 1593. Квадратная страна. Версия 2 | 10 июн 2014 11:43 | 2 |
#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. |
WA 29 | Soucup Adrian | 1593. Квадратная страна. Версия 2 | 7 июн 2014 19:47 | 3 |
WA 29 Soucup Adrian 2 июл 2012 21:53 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... |
Please, give some advices to solve this problem | ahmedov(NUUz_2) | 1593. Квадратная страна. Версия 2 | 30 сен 2013 06:10 | 10 |
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 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. |
Test 43 | Radostin Chonev | 1593. Квадратная страна. Версия 2 | 26 сен 2013 20:31 | 1 |
Test 43 Radostin Chonev 26 сен 2013 20:31 Can anyone help me ? I have WA on test 43 . Thanks for your attention . |
TLE 54, what is wrong with Java? | Hikmat Ahmedov | 1593. Квадратная страна. Версия 2 | 3 мар 2013 16:50 | 1 |
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, |
WA#15 | IgorKoval(from Pskov) | 1593. Квадратная страна. Версия 2 | 23 янв 2012 16:22 | 1 |
WA#15 IgorKoval(from Pskov) 23 янв 2012 16:22 |
test 20 | wiza | 1593. Квадратная страна. Версия 2 | 12 окт 2011 22:42 | 1 |
Input 7 Output 4 Edited by author 12.10.2011 22:59 |
TLE test 13 | doulce | 1593. Квадратная страна. Версия 2 | 12 ноя 2010 20:20 | 1 |
My algorithm is O(sqrt(n)). I dont know why it is TLE test 13. Any hints? |
My program used the least memory among all the ac programs :) | Sevenk | 1593. Квадратная страна. Версия 2 | 10 авг 2010 23:34 | 2 |
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! :) |
Does this need fast factorization (faster than O(sqrt(N)) ) ? | Roman Atangulov | 1593. Квадратная страна. Версия 2 | 19 июн 2009 17:13 | 6 |
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. Square country. Version 2 | Vladimir Yakovlev (USU) | 1593. Квадратная страна. Версия 2 | 7 фев 2009 12:31 | 7 |
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! int tmp = (long long) i*i; It was AC before new tests were added. ))))) Edited by author 07.02.2009 12:31 |