Sum of LCM ( 1 , n ) , LCM ( 2 , n ) , LCM ( 3 , n ) , ... , LCM ( n , n ) | C ++ implementation of the approach ; Euler totient Function ; Function to return the required LCM sum ; Summation of d * ETF ( d ) where d belongs to set of divisors of n ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define n  1000002 NEW_LINE #define ll  long long int NEW_LINE ll phi [ n + 2 ] , ans [ n + 2 ] ; void ETF ( ) { for ( int i = 1 ; i <= n ; i ++ ) { phi [ i ] = i ; } for ( int i = 2 ; i <= n ; i ++ ) { if ( phi [ i ] == i ) { phi [ i ] = i - 1 ; for ( int j = 2 * i ; j <= n ; j += i ) { phi [ j ] = ( phi [ j ] * ( i - 1 ) ) / i ; } } } } ll LcmSum ( int m ) { ETF ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = i ; j <= n ; j += i ) { ans [ j ] += ( i * phi [ i ] ) ; } } ll answer = ans [ m ] ; answer = ( answer + 1 ) * m ; answer = answer / 2 ; return answer ; } int main ( ) { int m = 5 ; cout << LcmSum ( m ) ; return 0 ; }