Inti Sets: Hackerank

Here is the original question.


In order to motivate his Peruvian students, a teacher includes words
in the Quechua language in his math class.


Today, he defined a curious set for a given positive integer N. He
called this set, an Inti set, and defined it as the set of all
positive integer numbers that have the number 1 as their single common
positive divisor with number N.


The math class about Inti sets was amazing. After class, the students
try to challenge to teacher. They each ask questions like this: "Could
you tell me the sum of all numbers, between A and B (inclusive), that
are in the Inti set of N?"


Since the teacher is tired and he's sure that you are the best in
class, he wants to know if you can help him.


Input Format


The first line of input contains an integer Q, 1 ≤ Q ≤ 20,
representing the number of students. Each of the next Q lines contain
three space-separated integers N, A and B, which represent a query.


Constraints


1 ≤ A ≤ B ≤ N ≤ 10^12


Output Format


The output is exactly Q lines, one per student query. For each query
you need to find the sum of all numbers between A and B, that are in
the Inti set of N, and print the sum modulo 1000000007.


Sample Input

2 
12 5 10 
5 1 4

Sample Output

12 10

Explanation


In the sample input, Q = 2, so you have to answer two questions:


In the first question N = 12, A = 5 and B = 10. So you have to find
the sum of all numbers between 5 and 10, that are in the Inti set of
12.


Inti set ( 12 ) = { 1, 5, 7, 11, 13, ... }


2 and 4 are not in the Inti set (12) because 12 and these numbers are
also divisible by 2.


3 and 9 are not in the Inti set (12) because 12 and these numbers are
also divisible by 3.


The numbers in the Inti set, which are in the query's range, are 5 and
7, so answer is ( 5 + 7 ) MOD 1000000007 = 12


In the second question, the numbers in t

The input numbers \$ A, B, N \$ can be as large as \$ 10^{12} \$, which
means that a Java int (which is a 32-bit signed integer) is not large
enough to hold all possible values, you should use long instead.

You also do not reduce the sum modulo 1000000007, as required.

The main function can be simplified by calculating the output for each
input line as it is read, this makes the queries array obsolete.

The function sumBetweenRange does not describe what the function actually does.
Something like sumOfIntiNumbersInRange or – using the mathematical term –
sumOfCoprimeNumbersInRange might be a better choice.

The main function would then look like this:

public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

    Scanner console = new Scanner(System.in);

    int queries = Integer.parseInt(console.nextLine());

    for (int i = 0; i < queries; i++) {
        long N = console.nextLong();
        long A = console.nextLong();
        long B = console.nextLong();

        long result = sumOfCoprimeNumbersInRange(A, B, N);
        System.out.println(result);
    }
}

Your method to determine if two numbers have a common factor is
very slow, it does trial division for all numbers between 2 and
no1/2. That can be improved slightly by using sqrt(no1) as the upper bound,
but one can do much better.

An efficient method is the
Euclidean algorithm
which determines the
greatest common divisor
of two integers. Two integers \$ a, b \$ have no common divisor exactly if \$ \gcd(a, b) = 1 \$.

There are many known Java functions for calculation the
greatest common divisor, see for example https://rosettacode.org/wiki/Greatest_common_divisor#Java.
Here is a simple (tail-recursive) implementation:

public static long gcd(long a, long b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

Then sumOfCoprimeNumbersInRange() can be implemented as

private static final int MOD = 1000000007;

// Compute the sum (modulo MOD) of all numbers in the range a...b which are coprime to N.
private static long sumOfCoprimeNumbersInRange(long a, long b, long n) {
    long sum = 0;

    for(long i = a; i <= b; i++){
        if (gcd(i, n) == 1) {
            sum = (sum + i) % MOD;
        }
    }
    return sum;
}

This is already much faster than your original implementation:
For \$ N=100000, A=10000, B=90000 \$ I measured on a
1.2 GHz Intel Core m5 MacBook:

• Your code: 3 seconds.

• GCD-based solution: 0.165 seconds.

But it may be not fast enough for the full range of numbers up to
\$ 10^{12} \$. A very elegant and efficient approach using the
Inclusion-Exclusion Principle is explained in

• How to count co-prime to n in a range [1,x] where x can be different from n?

on Stack Overflow.
Let us consider \$ N = 300 = 2^2 \cdot 3 \cdot 5^2 \$ as an example. The distinct prime
factors are \$ 2, 3, 5 \$, and to compute the sum of all numbers in some range which
are coprime to \$ N \$ one proceeds as follows:

• Compute the sum of all numbers in the range.

• Subtract the sum of all multiples of \$ 2, 3 \$, and \$ 5 \$ in the range.

• Add the sum of all multiples of \$ 2 \cdot 3, 2 \cdot 5 \$, and \$ 3 \cdot 5 \$ in the range.

• Subtract the sum of all multiples of \$ 2 \cdot 3 \cdot 5 \$ in the range.

Note that apart from the factorization, no trial divisions are required anymore, only
multiplications.

First we need a function to get the distinct prime factors of a given number,
e.g. the function in Finding out the prime factors of a number,
modified slightly to return only distinct prime factors:

// List of all distinct prime factors of n.
static List primeFactors(long n) {
    List factors = new ArrayList();
    long md = 2;
    if (n % md == 0) {
        factors.add(md);
        do {
            n /= md;
        } while (n % md == 0);
    }
    md = 3;
    while (md  1) {
        factors.add(n);
    }
    return factors;
}

Now the "challenge" is to translate the Inclusion-Exclusion approach to a
recursive function, and that could look as follows:

```
// Sum of all numbers 1...k, computed modulo MOD.
private static long sumUpTo(long k) {
k = k % MOD; // Otherwise the following multiplication can overflow.
let sum = k * (k+1) / 2;
return sum % MOD;
}

// Sum of all numbers (modulo MOD) in a...b which are divisible by k, but not
// by any multiple of k with factors in the primes list:
private static long inclExcl(long a, long b, long k, List primes) {

// Sum of all numbers in 1...b which are divisible by k:
long s1 = sumUpTo(b / k) * k;
// Sum of all numbers in 1...(a-1) which are divisible by k:
long s2 = sumUpTo((a-1) / k) * k;

long sum = (s1 - s2) % MOD;

for (int idx = 0; idx primes = primeFactors(n);

long sum = inclExcl(a, b, 1, primes) % MOD;
if (sum < 0) {
sum += MOD;
}
re

StackExchange Code Review Q#160241, answer score: 8