HackerRank Number Theory – A Weird Function

Challenge: A Weird Function

Subdomeniu: Number Theory (number-theory)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464744325

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/a-weird-function/problem

Cerinta

Ma5termind is going through the Euler's book of knowledge when he finds the following function: 

	def function(L,R):
    	sum=0
    	for i in range(L,R+1):				#[L,R]
            for j in range(1,i+1):			#[1,i]
            	cnt=0
            	if (j)*(j+1) == 2*i :
                	for k in range(1,i+1):	#[1,i]
                    	if __gcd(k,i)==1:	#__gcd Greatest Common Divisor 
                        	cnt+=1
                sum=sum+cnt
        return sum
        
The function seems weird as well as interesting. Don't you think ?? 

Fascinated by the function, Ma5termind codes it and successfully compiles it in the first go itself. After all, he is a good coder. Ma5termind checks the output computed by the function for all the values of $L$ and $R$ in the range $[1,100]$ and finds that the results are correct.

But as we all know, Ma5termind loves large numbers - very large numbers. When he inputs $L=1$ & $R=10^{12}$, the code does not produce any output #TimeLimitExceeded. He still wants to know the answer for such large ranges. Can you help him by writing a code that can also produce an answer for such large ranges?   

**Input Format**  
First line of input contains a single integer $T$ denoting the number of test cases. First and the only line of each test case contains two space separated integers $L$ and $R$ denoting inputs to the above function.  

**Output Format**  
Output consists of $T$ lines each containing result computed by the function when corresponding range is inputted to the function.

**Constraints**  
$1 \le T \le 10^5$  
$1 \le L \le R \le 10^{12}$

**Sample Input**  

    2
    1 10
    2 5

**Sample Output**  

    9
    2

**Explanation**  
Pass Parameters to the function and check the result.

Cod sursa

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define debug(x) cout << #x << " = " << x << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
inline ll Mod(ll x, ll mod) { return x % mod >= 0 ? x % mod : x % mod + mod; }

const ll N = 2000000;
ll Phi[N];
ll phiphi[N + 1];
ll prefix[N];
vector<int> primes;

void find_primes(ll n)
{
    int lp[n + 1] = {0};
    for (int i = 2; i <= n; ++i)
    {
        if (lp[i] == 0)
        {
            lp[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; j < (int)primes.size() && primes[j] <= lp[i] && i * primes[j] <= n; ++j)
            lp[i * primes[j]] = primes[j];
    }
}

int upper(ll r)
{
    ll q = sqrt(2 * r);
    q -= 3;
    for (int i = 0; i < 6; i++)
    {
        if (q * (q + 1) / 2 > r)
        {
            return q - 1;
        }
        q++;
    }
    return -1;
}

int lower(ll l)
{
    ll q = sqrt(2 * l);
    q += 3;
    for (int i = 0; i < 6; i++)
    {
        if (q * (q + 1) / 2 < l)
        {
            return q + 1;
        }
        q--;
    }
    return -1;
}

void factorize(int n, vector<int> &s)
{
    for (int i : primes)
    {
        if (i * i > n)
            break;
        if (n % i == 0)
        {
            s.emplace_back(i);
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        s.emplace_back(n);
}

ll phi(ll i)
{
    vector<int> prime_factors;
    prime_factors.reserve(40);
    if (!(i % 2))
        i /= 2;
    factorize(i, prime_factors);
    for (int k : prime_factors)
    {
        i -= i / k;
    }
    return i;
}

void prepare()
{
    primes.reserve(150);
    find_primes(1500);
    phiphi[1] = 1;
    for (ll i = 1; i < N + 1; i++)
        phiphi[i] = phi(i);
    for (int i = 1; i < N; i++)
        Phi[i] = phiphi[i] * phiphi[i + 1];
    prefix[0] = 0;
    for (int i = 1; i < N; i++)
        prefix[i] = prefix[i - 1] + Phi[i];
}

ll solve(ll l, ll r)
{
    int R = upper(r);
    int L = lower(l);
    //cout << R << " " << L << '\n' ;
    return prefix[R] - prefix[L - 1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    prepare();
    int t;
    cin >> t;
    while (t--)
    {
        ll l, r;
        cin >> l >> r;
        cout << solve(l, r) << '\n';
    }
}