Приветствую всех! На днях я решал задачу, в которой требовалось определить, представимо ли число N < 1015 в виде суммы двух квадратов. И у меня возникли проблемы с этим, банальный перебор за корень давал TL. Так же пробовал разложить на простые сомножители за тот же корень, и потом проверял четность степеней у простых делителей вида 4k + 3, опять же TL. Скорее всего задача сдается за корень, и мне интересно именно техническая реализация этого, т.е. как конкретно писать аккуратный перебор или факторизацию за корень, и в чем конкретно проявляется эта аккуратность. Если что, эта задача с тимуса link HERE Заранее благодарен!
Заводим 2 указателя i и j. Изначально i = 1,
. На каждой итерации увеличиваем i на единицу, а j уменьшаем до тех пор, пока i2 + j2 > n. Когда-нибудь получится, что i2 + j2 = n. Либо не получится, если число непредставимо в виде суммы двух квадратов.
Вот кусок моего кода, который я сдавал где-то год назад:
Большое спасибо!
Можно же просто завести 1 "указатель", а второй считать, просто идти не до n а до корня
тогда будет тратиться время на извлечение корня в double. Может получиться дольше, наверно)
Если я правильно понял, то на каждой итерации у вас будет вызываться функция sqrt. Такое решение невозможно сдать из-за TL, всё-таки извлечение корня — довольно трудоемкая операция.
Ок.
У меня прошло и с sqrt. Код
Весело. Что-то я не подумал так ускорить. У меня было немного более "влоб" и падало по тайму где-то после 10ого теста.
корень не обязательно каждый раз извлекать, можно что-то возводить в квадрат, а можно воспользоваться тем что (x+1)^2 == x^2+2x+1 и каждый раз прибавлять/вычитать 2x+1
Вроде еще можно предпросчитать квадраты в хеш таблицу до 10^7, тогда непокрытых будет немного. Я как то так сдавал когда-то.
How can you use an algorithm that checks
N = a²+b²in the problem you linked? It asks for the minimum number of squares that sum to N, am I right?a little hint
http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem
Any natural number can be represented as the sum of four integer squares. We check that N = a2. If not, we check that N = a2 + b2. If this is not correct, we check that N = a2 + b2 + c2. And the answer is 4, if this is also not correct.
how can we check if N can be represented as a sum of three squares fast?
The following question on MathOverflow might help: http://mathoverflow.net/questions/57981/testing-whether-an-integer-is-the-sum-of-two-squares
EDIT: Sorry, I misread your comment :)
IMHO, in that problem more easy to check if N can be represented as sum of 1,2,4 squares. Else — 3. :-)
27 = 1*1 + 1*1 + 3*3 + 4*4 = 1*1 + 1*1 + 5*527 != a*a27 != a*a + b*bFail.
if N != (8*t+7)*4^k then there are 3 squares.
oh, don't you know the proof or some link with the proof?
And now read your previos explanation.
sorry, I've misunderstood you
It returns 0, if x is not a sum of three squares.
How come?
This is a very difficult method of pen and paper :)
I think that algorithm follows this: http://www.proofwiki.org/wiki/Integer_as_Sum_of_Three_Squares
For sum of two squares, how can it be modified?
Don't answer him. This is one of the problems from a running contest.
Sorry?
Motori
according to me we can run a loop in which 'i' goes from 1 to sqrt(N/2) and if N-i*i is a perfect square we are done....
for(int i=1; i*i<=N/2; i++) { if((N-i*i) is a perfect square) done; }
its complexity is O(sqrt(N)).....
How do you check number for square? I did the same and used sqrt() and got TL.
An arbitrary positive number n is expressible as the sum of two squares iff, given its prime factorization
n=p1^(a1)p2^(a2)p3^(a3)...pk^(ak),
none of pi^(ai) +1 is divisible by 4 (Conway and Guy 1996, p. 147). http://mathworld.wolfram.com/SquareNumber.html