# Find Gcd summation fast?

Find the value of the summation:

$$val=\left( \sum_{i=1}^a \sum_{j=1}^b\sum_{k=1}^c....\sum_{x=1}^p GCD(i,j,k,..x) \right)$$

Contraints

$2\leq$number of summation terms$\leq 500$, $1\leq a,b,c....p\leq 100000$

I applied brute force solution to solve it, but it takes too much time which is not acceptable

• please show us what you have done.. – Apurv Jan 18 '14 at 17:36
• i applied brute force it took lot of time – azdssdf Jan 18 '14 at 17:40
• add that to the question.. – Apurv Jan 18 '14 at 17:41
• A brute force that might take less time, and even lead to a closed form formula: Loop over all possible values of the gcd, try to figure out often that value appears in the sum. This approach can perhaps be refined a lot further. – Harald Hanche-Olsen Jan 18 '14 at 17:42
• Or you could try to add one variable at a time, using that $\gcd(i,j,\ldots,x,y)=\gcd(\gcd(i,j‚\ldots,x),y)$. Possibly combine that with my previous suggestion. There seem to be lots of things one can try. – Harald Hanche-Olsen Jan 18 '14 at 17:45