|
|
back to boardUse 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 can't understand you 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. |
|
|
