Theory:
Perfect square problem.Problem is to determine a pair of numbers where the small (lower_num) number divides the numbers from 1 up to higher_num into two groups in a way that summation of 1 to (lower_num-1) is equal to summation of the numbers from (lower_num+1) to higher_num.
Expanation: first pair 6 8
summation of 1 to 5 = 5*(5+1)/2 = 15
summation of 7 to 8 = 7+8=15
so, 5*(5+1)/2 = 8*(8+1)/2-6-5*(5+1)/2, here n*(n+1)/2 formula is used.
so if we assume the lower_num=divider;
then (divider-1)*divider/2=summation of 1 to higher_num – divider – (divider-1)*divider/2.
=> (divider-1)*divider + divider = summation of 1 to higher_num;
=> divider^2 – divider + divider = Sum_hi;
=> divider = sqrt of Sum_hi;
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <cstdio> #include <cmath> #define lld long long using namespace std; int main() { double db; lld a,b,lp,hp; int cnt=1; double i=8; while(cnt<11) { db=sqrt(i*(i+1)/2); a=db; if(a==db) { //cout<<a<<" "<<i<<"\n"; printf("%10ld%10ld\n",a,long(i)); cnt+=1; } i+=1; } return 0; } |