SPOJ --- NAJPWG - Playing with GCD

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;

typedef long long unsigned llu;

ll arr[100009];

void phi()

{

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

        arr[i]=i;

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

        if(arr[i]==i)

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

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

}

void calculate()

{

    arr[1]=0;

    arr[2]=1;

    for(ll i=3;i<=100000;i++) arr[i]=arr[i-1]+(i-arr[i]);

}

int main()

{

    phi();

    calculate();

    ll tst,num,ca=1;

    cin>>tst;

    while(tst--)

    {

        cin>>num;

        cout<<"Case "<<ca++<<": "<<arr[num]<<endl;

    }

    return 0;

}

///Alhamdulillah

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