I have thought about the following algo based on inclusion exclusion principle to solve this problem:
- iterate through all 2^5 - 1 subsets of a, a+d, a+2d, a+3d, a+4d
- get the count of numbers divisible by the subset numbers
- include or exclude based on the number of divisors involved in the subset
- print the complement of this count to get numbers which are not divisible.
My program in java passing the sample input tests, but gives a TLE on submitting.
Here’s my code:
private static long solve(InputReader sc) {
int n = sc.nextInt(), m = sc.nextInt(), a = sc.nextInt(), d = sc.nextInt();
int[] div = {a, a+d, a+2*d, a+3*d, a+4*d};
long count = 0;
for (byte i = 0 ; i < 2 ; i++) {
for (byte j = 0; j < 2; j++) {
for (byte k = 0; k < 2; k++) {
for (byte l = 0; l < 2; l++) {
for (byte o = 0; o < 2; o++) {
int divisible = 1;
int eleCount = 0;
if (i == 1) {
divisible *= div[0];
eleCount++;
}
if (j == 1) {
divisible = lcm(divisible, div[1]);
eleCount++;
}
if (k == 1) {
divisible = lcm(divisible, div[2]);
eleCount++;
}
if (l == 1) {
divisible = lcm(divisible, div[3]);
eleCount++;
}
if (o == 1) {
divisible = lcm(divisible, div[4]);
eleCount++;
}
if (eleCount == 0) {
continue;
}
int sign = eleCount % 2 == 0 ? -1 : 1;
count += sign * getDivCount(n, m, divisible);
}
}
}
}
}
return m - n + 1 - count;
}
static int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
if (a == b)
return a;
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
static int lcm(int a, int b) {
return (a*b)/gcd(a, b);
}
private static long getDivCount(long n, long m, long x) {
return (m / x) + 1 - ((long) Math.ceil(((double) n) / x));
}
Any hint on this is much appreciated.