3
\$\begingroup\$

I came across this question in a coding contest (Java-restricted) and I got TLE. I am unable to provide the link of the question as the contest is closed now. Can I know how can I optimise this?

Four Functions

Given four functions

  • A(x) = Number of i where 1 <= i <= x and gcd(i,x) = 1
  • B(x) = Sum of A(d) where d divides the number x
  • C(x) = Sum of exponents of each prime in the prime factorization of B(x)
  • D(x) = Sum of C(i) where 1 <= i <= x

If $$B(x) = {p_1} ^ {a1} {p_2} ^ {a2} {p_3} ^ {a3}$$ where p1,p2,p3 are prime factors of B(x), then C(x) is a1 + a2

Find the value of D(N) Constraints:

$$1 \le testcases \le 1000000$$

$$1 \le N \le 1000000$$

Example :

Input :

1

4

Output :

4

For n = 4

$$C(1) = 0$$

$$C(2) = 1$$

$$C(3) = 1$$

$$C(4) = 2$$

$$D(4) = C(1) + C(2) + C(3) + C(4) = 4$$

This is my approach

public class Main {
    static long commonDivisor(long num1,long num2) {
        if(num1 == 0) {
            return num2;
        }
        return commonDivisor(num2 % num1, num1);
    }

    static long funcA(long numb) {
        long answer = numb;
        for (long itr = 2; itr * itr <= numb; itr++) {
            if(numb % itr == 0) {
                while(numb % itr == 0) {
                    numb /= itr;
                }
                answer -= answer / itr;
            }
        }
        if(numb > 1) {
            answer -= answer / numb;
        }
        return answer;
    }
    static long funcB(long numb) {
        long sum = 0;
        for (long itr = 1; itr <= Math.sqrt(numb); itr++){
            if (numb % itr == 0){
                if(numb/itr == itr){
                    sum = sum + funcA(itr);
                } else {
                    sum = sum + funcA(itr) + funcA(numb/itr);
                }
            }
        }
        return sum;
    }
    static boolean check_prime(long numb) {
        BigInteger bigint = new BigInteger(String.valueOf(numb)); 
        return bigint.isProbablePrime(1); 
    }
    static long funcC(long numb) {
        if (numb <= 1) {
            return 0;
        }
        long remNum = numb;
        long expo = 0;
        for (long itr = 2; itr <= Math.sqrt(numb); itr++) {
             if(check_prime(itr)) {
                while (remNum % itr == 0) {
                    expo++;
                    remNum /= itr;
                }
             } 
        }
        if(check_prime(remNum)) {
            if (remNum > 1) {
                expo++;
            }
        }
        return expo;
    }
    static long funcD(long numb) {
         long result = 0;
         for(long itr = 1; itr <= numb; itr++){
             result += funcC(funcB(itr));
         }
         return result;
    }

    public static void main(String[] args) {
        try {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));    
        long testCases = Long.parseLong(buffer.readLine());
        for(long itr = 1; itr <= testCases; itr++) {
            long number = Long.parseLong(buffer.readLine());
            System.out.println(funcD(number));
        }
    } catch(Exception e) {
        System.out.println("Error");
    }
}
\$\endgroup\$
1

1 Answer 1

6
\$\begingroup\$

For a coding contest, the answer is almost never to implement the problem the same way as it is given.

For example here, functions A and B are actually intentionally misleading. Function A is also known as Euler's Totient, and function B computes the sum of totients of divisors which is the same as the original number. Detailed review of them is therefore a waste, functions A and B don't need to be implemented at all.

Function C can be improved by noting that the lowest divisor of a number is necessarily a prime, so calling check_prime is unnecessary. If itr was a * b then a and b would have been found first and divided out of remNum already, making itr not a divisor of remNum. The square root is also unnecessary, and relatively expensive. It can be avoided by testing itr * itr <= numb instead. There is no risk of overflow given that numb <= 1000000. Further refinements are possible.

Function D can be improved by caching the partial sums. In isolation that would not help, but there can be multiple test cases during a run of the program, and they can reuse the previously computed sums. For example as an extreme case, after the test case 1000000 has been used, any further test cases could be essentially free, because all possible cases would have been calculated at that point. Also, after funcD(10) has been evaluated, funcD(20) could start with that result instead of starting over from scratch.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Just an addendum to the last part. The function $D$ can also be simplified. The function $C$ satisfies the logarithmic property $C(a)+C(b)=C(ab)$. Therefore $D(n)=C(n!)$. Now, $C(n!)$ can be computed using Legendre's formula by computing the primes up to $n$ and applying the formula to compute their exponents (or valuations) in the factorization of $n!$. \$\endgroup\$
    – plop
    Apr 9, 2021 at 13:35

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .