problem Link :

The depth of phi value of a number is denoted by the number of steps required before it reaches 1. An example will make it very clear. ϕ(13) = 12 . . . step1 ϕ(12) = 4 . . . step2 ϕ(4) = 2 . . . step3 ϕ(2) = 1 . . . step1 So the depth of phi(13) is 4. We name this function as depthphi. So we can write depthphi(13) = 4. The sum of depthphi function (SODF) takes two integers as parameter and its definition is given below: SODF(m, n) = ∑ n i=m depthphi(i), m ≤ n Given the value of m and n your job is to find the value of SODF(m, n). The following paragraph is extracted from Mathworld to inform you about phi function. The totient function ϕ(n) or phi(n), also called Euler’s totient function, is defined as the number of positive integers ≤ n that are relatively prime to (i.e., do not contain any factor in common with) n, where 1 is counted as being relatively prime to all numbers. Since a number less than or equal to and relatively prime to a given number is called a totative the totient function ϕ(n) can be simply defined as the number of totatives of n. For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so ϕ(24) = 8 . The totient function is implemented in Mathematica as EulerPhi[n]. Input The first line of the input file contains an integer N (0 < N < 2001) which indicates how many sets of inputs are there. Each of the next N lines contains two integers m and n (2 ≤ m ≤ n ≤ 2000000). Output For each line of input produce one line of output. This line contains an integer S, which actually denotes the value of SODF(m, n).

Sample Input 2 2 10 100000 200000

Sample Output 22 1495105

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <bits/stdc++.h>

using namespace std;
#define N 2000001
vector<int> eulerPhi;
vector<int> depthPhi;
vector<int> sumDepth;

// eulerphi(x) = x * (1-1/PF) for all PF of x
void modifiedSieve(){
    eulerPhi.assign(N, 0);
    for(int i=0; i i+It N; i++) eulerPhi[i] = i;
    depthPhi.assign(N, 0);
    sumDepth.assign(N, 0);
    for(long long i=2;i i+It N;i++){
        // eulerphi(i) = i-1 if i is a prime number
        // thus, prime number can be checked using eulerphi
        if(eulerPhi[i] == i) {
            for(long long j=i;j i+It N;j+=i){
                eulerPhi[j] -= eulerPhi[j]/i; // remove fraction
        depthPhi[i] = depthPhi[eulerPhi[i]] + 1;
        sumDepth[i] = sumDepth[i-1] + depthPhi[i];

int main()
    int tc,m,n;
    while(tc--) {
        scanf("%d %d",&m,&n);
        printf("%d\n", sumDepth[n]-sumDepth[m-1]);

Copy The Code & Try With Live Editor


2 10
100000 200000




UVA Online Judge solutio - 10990-Another New Function - UVA Online Judge solution in C,C++,java

UVA Online Judge solutio - 1099-Sharing Chocolate - UVA Online Judge solution in C,C++,java
UVA Online Judge solution -11002-Towards Zero - UVA Online Judge solution in C,C++,java