|
|
вернуться в форумПоказать все сообщения Спрятать все сообщенияUse the formula:
N=[a+(a+p-1)]*p/2,and you will got the formula of A:
A=[ 2*N/P +1-p]/2
Loop p to find A,that's what someone else in this forum suggested.
But even in this way some people got TLE as well.I guess you start looping P from 10^9...
In fact you can find that 2N/P +1-P >0,solve this inequality,you will find p is <[1+sqrt(1+8N)]/2.
You can cut the time of the loop down to half or even less in this way. I'll explain it to you in Chinese tomorrow...How did you find my post? this problem has solution O(sqrt(2N))
'cause 2N = P(2A+P-1)
N, P, A is natural, so P is divider of 2N, so algo is simple
scan N, multiply N by 2, then for each divider of this new N less then sqrt(N) try to find p = divider or n / divider, a = (a - p + 1) / 2, where a supposed to be natural, if out p bigger than our saved one - replace saved one.
out our bigger result Loop P from 44720 downto 1 and check out these two conditions to be true:
1) N>=P(P+1)/2;
2) P divides (N-P(P+1)/2).
Break as fast as you find the first one. Then A=1+(N-P(P+1)/2)/P.
If you still can't get it, look at the following lines.
1+2+3+4+5=15
2+3+4+5+6=20
3+4+5+6+7=25
4+5+6+7+8=30
Et cetera. |
|
|
