Somewhat similar to SRM 613 550-pointer Random GCD. Both of them are nice.
1 Like
I used this approach only.
[My code][1].
It was giving TLE in the last case.
Finally to reduce my time taken I changed some things.
- I prime factorized every number till the maximum M provided in all the test cases.
- As the power was raised by N for every number. I saved power of N for every prime.
- When I calculated the power of any number. I just multiplied power of each prime it consisted of(and how many powers of that prime it consisted of).
[2]
It also gave TLE. I figured that for 2,3,5,7 for storing primes it would require additional M/2,M/3,M/5,M/7 computations.
So, I started storing primes from 11 rather than 2 and when I calculated the power of a number. I first calculated the powers of 2,3,5,7 it has then used the prime factorization I pre-computed.
It was just under the time limit. [Final Code][3]. Time - 14.92 seconds.
I just managed to get it under the time limit. There might be another solution as I have seen people with much less time.
It would really be helpful if any other solution to this problem can be posted here.
[1]: http://www.codechef.com/viewsolution/5549972
[2]: http://www.codechef.com/viewsolution/5552506
[3]: http://www.codechef.com/viewsolution/5560673
2 Likes
I applied the same approach mentioned in the editorial . But one thing to notice is that is if m/d1= m/d2 then B[d1] = B[d2] then we do not need to check when to calculate modulo…
Proof can be found by considering the lemmas mentioned by Lalit Kundu in this link http://www.quora.com/What-is-the-approach-to-solve-Hyperrectangle-GCD-problem-of-Codesprint5-URL-for-the-problem-HackerRank
my solution CodeChef: Practical coding for everyone
1 Like
Please Explain what are arrays A and B representing.
I think a better solution exists.
Got AC in 0.46 sec.
Just take a look at my solution.
5 Likes
I used the fact that the number of arrays of N elements between 1 and X with GCD equal to 1 is:
a(X, N) = sum(µ(k)*floor(X/k)^N, k=1…n) where µ is the Möbius function.
And the number of arrays of N elements between 1 and M with GCD equal to D is: a(floor(M/D), N)
The final answer is sum(a(floor(M/D), N), D=L…R)
By using the same approach as in SEPT14/FLOORI4, we can compute the first sum in O(log(N) sqrt(M)) which makes the complexity of the computation of the second sum: O(log(N) sqrt(M) sqrt(M))
And as we can precompute µ(k) for k between 1 and M in O(M log(M)), the total Complexity is O(M log(M) + M log(N))
Here is my solution: 5533797
2 Likes
Hello all i followed this approach
please review code from CodeChef: Practical coding for everyone
Algorithm:-
Fact:
1)‘r’ objects can be arranged in ‘n’ places with repetitions :Math.pow(r,n);
2)if d is the GCD of n numbers then all n(at least one ==d) numbers are divisible by d
I have applied above facts to solve this problem
For each test case
allFactors is list that can store all numbers divisible by all d’s
for all d(L to R)
localFactors: is list that can store all numbers divisible by current 'd'
1)store all numbers(<=M) divisible by d(including d) in localFactors
2)Get the size of localFactors
3)Now the Math.pow(size,n)%mod give all the GCD of numbers stored in localFactors
4)Now localFactors contains numbers for those
a)the GCD out of Range that is >R
a.1)this can be eliminated by finding how many(Rc) out of Range >R
a.2)subtract Math.pow(Rc,n)%mod from 3
b) GCD alreader included in previous iteration
for all numbers(dr) common to both localFactors and allFactors
b.1)get count(cd) of numbers(<=M) that can be divisible by 'dr'
b.2)subtract Math.pow(cd,n) %modfrom 4)a.2
5)clear all localFactors.clear()
end for
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
public class Main {
public static int getFactorCnt(int num, int M) {
int count = 0;
count=(M-num)/num;
return count+1;
}
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
int t = Integer.parseInt(br.readLine());
String d[] = null;
long mod = 1000000000 + 7;
long result = 0;
int N = 0, M = 0, L = 0, R = 0;
HashSet<Integer> gcdGlobalFactor = new HashSet<Integer>();
ArrayList<Integer> gcdoutOfRange = new ArrayList<Integer>();
ArrayList<Integer> gcdlocalFactors = new ArrayList<Integer>();
int fc = 0;
long modCnt = 0;
for (int i = 0; i < t; i++) {
result = 0;
d = br.readLine().split(" ");
N = Integer.parseInt(d[0]);
M = Integer.parseInt(d[1]);
L = Integer.parseInt(d[2]);
R = Integer.parseInt(d[3]);
gcdGlobalFactor.clear();
for (int D = L; D <= R; D++) {
gcdoutOfRange.clear();
gcdlocalFactors.clear();
if(gcdGlobalFactor.contains(D)){
continue;
}
for (int j = 2; j < M + 1; j++) {
if (D * j <= M) {
if(D*j>R){
gcdoutOfRange.add(D*j);
}
if(gcdGlobalFactor.contains(D*j)&&(D*j<=R)){
gcdoutOfRange.add(D*j);
}
gcdGlobalFactor.add(D * j);
gcdlocalFactors.add(D*j);
} else {
break;
}
}
int len = gcdlocalFactors.size();
if (len == 0) {
result +=1;
result = result % mod;
continue;
}
modCnt = (long) Math.pow(len+1, N);
result += modCnt;
len=gcdoutOfRange.size();
for (int j = 0; j < len; j++) {
fc = getFactorCnt(gcdoutOfRange.get(j), M);
result = (long) (result - Math.pow(fc, N));
}
result = result % mod;
}
System.out.println(result);
}
} catch (NumberFormatException | IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
I am unable to understand the question. will somebody explain with an example. What will the initial array contain? do we have arrays of arrays?
Can Anybody tell what’s wrong with this solution. I am getting WA for this
http://www.codechef.com/viewsolution/5793327
If some one look this it will be great hel[ to me
CodeChef: Practical coding for everyone
Regards
Samuel
Hello all Please review my code
CodeChef: Practical coding for everyone
please let me know why it is not working
Regards
Samuel
I like this one, it was nice 
Can you explain what you precompute in array A?
A[i] tells me total no. of possible ways in which n nos are selected from 1 to i so that GCD is 1.
Now as told A[i] = (tot of possible ways) - sum(gcd=2,3,…,i)
(GCD=2)=A[i/2] as explained,and so on.
what I do is I combine (GCD=i/3+1)to(GCD=i/2) in 1 slot as all of them is equal to A[2], (GCD=i/4+1)- (GCD=i/3) in 1 slot = A[3], and so on…, which are already computed.
Now for any m u can also see u only need 2*sqrt(m) values A[1], A[2], A[3],…A[sqrt(m)], A[m/sqrt(m)],…A[m/2],A[m/1].
This is because for all l<=k<=r u can calculate no of possible ways st gcd=k using array A.
4 Likes
Thank you 
Why you do not add link to your previous comment instead of bad formatted code?
It was a good question