SOPC019 Editorial

PROBLEM LINK:

Practice
Contest

Author: Shriram Chandran
Editorialist: Shriram Chandran

DIFFICULTY:

Medium

PREREQUISITES:

Math

PROBLEM:

Given a number N, compare the Euler Totient function to number of factors of all numbers less than or equal to N.

EXPLANATION:

Here it is required to note that a function g(p,k) defined as f(p^k)/\varphi (p^k) for prime p and natural k is always decreasing in p and k, and is greater than 1 for a handful of values of p and k only. One can subsequently prove that the only numbers with \varphi(N)=f(N) are 1,3,6,10,18,24 and 30, while the only numbers with \varphi(N)<f(N) are 2,4,8 and 12. For all other natural numbers, \varphi(N)>f(N).

This counting can now be done in various ways - brute force till 31 and directly hard code as (N-11,4) for the rest, or store the above values in two arrays and count the number of numbers lesser, etc.

The rigorous math proof of the above is skipped. However, it is simple and is left as an exercise to the reader.

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
    ll n;
    cin>>n;
    ll ans1,ans2;
    if(n<31)
    {
        ans1=ans2=0;
        ll i=2;
        while(true)
        {
            if(i==n+1)
                break;
            ll etf=1;
            ll temp=i;
            ll nof=1;
            if(temp%2==0)
            {
                ll calc=0;
                while(temp%2==0)
                {
                    calc++;
                    temp/=2;
                }
                etf*=pow(2,calc-1);
                nof*=(calc+1);
            }
            for(ll j=3;j*j<=temp;j++)
            {
                ll calc=0;
                while(temp%j==0)
                {
                    calc++;
                    temp/=j;
                }
                if(calc)
                {
                    etf*=(pow(j,calc-1)*(j-1));
                    nof*=(calc+1);
                }
            }
            if(temp>2)
            {
                etf*=(temp-1);
                nof*=2;
            }
            if(etf>nof)
                ans1++;
            else if(etf<nof)
                ans2++;
            i++;
        }
    }
    else
    {
        ans1=n-11;
        ans2=4;
    }
    cout<<ans1<<" "<<ans2<<endl;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}