Adding Fractions

Source: CodeChef April Challange. See here

Problem: You have an array A of length n with each entry stroing a fraction a/b.
Define B[i] as length of sequence starting at i such that sum of fractions of this sequnce is largest amongst all sequnces beginning at i. Sum of a/b & c/d is defined to be (a+b)/(c+d).
Compute Array B given A.

LCM Sum

Source : CodeChef

Problem: Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.

Update:  Solution given by a friend Tarundeep posted  in comments.