algorithm - Understanding the code for finding the permutation of numbers x and y,(less than n) such that x*y is a perfect square and y -x is maximum (x < y) -
i read function in programming blog aforementioned task,but i'm unable understand . (also x*y should maximum).also preference maximizing x*y more y-x .
long long ans = 0; int x,y; for( = 2;i <= n / i;++i){ int k = n / (i * i); int y = k *i*i; int x = k * (i - 1) * (i - 1); if((long long)x * y > ans){ ans = (long long)x * y; x = x; y = y; } }
i <= n / iensures valuesx,ylessn, derived square ofi, inside loop.
(kderivedn,i. ,x,yin turn derivedk,i.)int k = n / (i * i);,int y = k * * i;,int x = k * (i - 1) * (i - 1);ensures valuex * yperfect square.
(sincex * y=k * k * * * (i - 1) * (i - 1). i.ex * yperfect square ofk * * (i - 1)).
also,xlessybecausexderives(i - 1)whereasyi.- the 3 statements in
ifloop @ end keep track of pair having largestx * y.
Comments
Post a Comment