How do we efficiently compute the value of expression given below?

Question

How to compute the value of following expression efficiently?

$$\sum_{x=1}^N\sum_{y=1}^N \frac{xy}{\gcd(x,y)^2}$$

I tried by my self but I am getting TLE with my solution.

Problem from HackerEarth.

Answer 1

below is my solution for the problem. but I am getting TLE in some of the test cases. could anyone help me on this to improve the complexity?

include

define ll long long

using namespace std;

const unsigned ll MOD = 1000000007;

ll gcd(ll a, ll b) {

if(b == 0){
    return a;
}
return gcd(b, a%b);

}

ll compute(ll n) {

ll ans =0;
for(ll i =1; i <= n; i++) {
    for(ll j =i; j <= n; j++) {
        ll g =0, lm =0, r =0;
        g = gcd(i, j);
        r = (i*j)/(g*g);
        if(i == j) {
           ans = (ans+r)%MOD; 
        } else {
            ans = (ans+2*r)%MOD;
        }
        ans %= MOD;
    }
}
return ans;

}

int main() {

ll n;
cin>>n;
ll ans = compute(n);
cout<<ans<<endl;
return 0;

}

Answer 2

You can halve your computations by noticing the sum is symmetric in $x$ and $y$ so that:

$$S=N+2\sum_{1\le x<y\le N}\frac{xy}{\gcd(x,y)^2}$$

Since you have the dynamic-programming tag, I'll also mention that the $\gcd$ can be computed dynamically. It suffices to use

$$\gcd(x,y)=\begin{cases}x,&x=y\\\gcd(y,x),&x>y\\\gcd(x,y-x),&x<y\end{cases}$$

or the usual $\gcd(x,y)=\gcd(y,x\%y)$. By caching the results here, a lot of recomputation can be avoided.