i need to solve this equation efficiently
m+n-gcd(m,n)=N
i.e, when N is given i need to find NUMBER OF PAIRS of m,n that satisify the equation ( also for ex: 45,100 is same as 100,45 )
here is what i do
N<10^6Code:lim=N/2; for(i=2;i<=lim;i++) { for(j=N-i+1;j<=N;j++) if(i+j-gcd(i,j)==N) count++; } printf("%d",count+2);
can any 1 help !!!