UVAOJ - 11064 - Number Theory

Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2005

Idea: Phi value of a number is the total value that make GCD=1, with the number n.The divisors are the numbers that make GCD of the number n.
So,
      total value = n - phi(n) - number of divisors of n.


Code First Then See Sloution

Code:
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define mx 1000789

char a[mx+6];
int phi[mx+6];
vector <ll> v;


void seive()
{
    memset(a,0,sizeof(a));
    for(ll i=3;i<=sqrt(mx);i+=2)
    {
        if(a[i]==0)
        {
            for(ll j=i*i;j<=mx;j+=i)
                a[j]=1;
        }
    }
    v.push_back(2);
    for(int i=3;i<=mx;i+=2)
    {
        if(a[i]==0)
            v.push_back(i);
    }
}

int main()
{
    ll n;
    seive();
    while(cin>>n)
    {
        ll t=n,sum=1,k=n;
        if(n==1||n==2)
        {
            cout<<0<<endl;
            continue;
        }
        for(int i=0;i<v.size()&&v[i]<=sqrt(n);i++)
        {
            if(n%v[i]==0)
            {
                ll cnt=0;
                while(n%v[i]==0)
                {
                    cnt++;
                    n/=v[i];
                }
                t=(t/v[i])*(v[i]-1);
                sum*=(cnt+1);
            }
        }
        if(n>1)
        {
            sum*=2;
            t=(t/n)*(n-1);
        }
        sum--;
      cout<<k-sum-t<<endl;
    }
    return 0;
}