SPOJ --- GCDEX - GCD Extreme

I just solve this problem after well understanding of euler totient function.
First of all we solve simple problem ∑ni=1gcd(i,n)$\sum _{i=1}^{n}gcd(i,n)$. How can you solve this.
We can write this function as ∑g∗cnt[g]$\sum _{}g\ast cnt[g]$
where g is gcd of pair(i,n). and cnt[g] =total number of pair having gcd g. And we simply need summation of this. Thanks to following gcd identity
As we know gcd(a,b)=g, then gcd(a/g,b/g)=1
then our equation simply becomes ∑d|nd∗phi[n/d]$\sum _{d|n}^{}d\ast phi[n/d]$
where phi[] is euler totient number.(only divisors because gcd of pair(i,n) can only be divisors of n). After that it is simple iterator over divisors of n and sum all value d*phi[n/d].
Now came to original question now we need all pair(i,j) in summation place. That is for each value of i from 1 to n ∑ni=1gcd(i,n)$\sum _{i=1}^{n}gcd(i,n)$. But we have to preprocess all values of phi[i] , d*phi[n/d] and some other.

Example:

Think about 5

5 has two divisor 1,5

1*phi[1/5]+5*phi[5/5]=(1*4)+(5*1)=9

then from 9 we need minus 5 = 4 for 4 pair{(1,5),(2,5),(3,5),(4,5)}

Like this we need to iterate 1 to 4{1=0,2=1,3=2,4=4}

All sum up=0+1+2+4+4=11

That is answer

Bismillahir Rahmanir Rahim

///Author: Tanvir Ahmmad

///CSE,Islamic University,Bangladesh

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<iterator>

#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array

/*every external angle sum=360 degree

  angle find using polygon hand(n) ((n-2)*180)/n*/

///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b

using namespace std;

typedef long long ll;

ll phi[1000001],gcd_1_n[1000001],ans[1000001];

void totient()

{

    for(ll i=1; i<= 1000000; i++)

        phi[i]=i;

    for(ll i=2; i<= 1000000; i++)

        if(phi[i]==i)

            for(ll j=i; j<=1000000; j+=i)

                phi[j]-=(phi[j]/i);

}

void divisor()

{

    totient();

    for(ll i=1; i<= 1000000; i++)

        for(ll j=i;j<=1000000;j+=i) gcd_1_n[j]+=(i*phi[j/i]);

    for(ll i=1; i<= 1000000; i++) gcd_1_n[i]-=i;

    for(ll i=1; i<= 1000000; i++) ans[i]=ans[i-1]+gcd_1_n[i];

}

int main()

{

    divisor();

    ll num;

    while(scanf("%lld",&num),num)

        printf("%lld\n",ans[num]);

    return 0;

}

///Alhamdulillah

Problem Link: https://www.spoj.com/problems/GCDEX/