Help needed SPOJ EASYMATH

Revision en2, by __zac__, 2020-07-30 17:43:02

I'm trying to solve this problem on SPOJ using inclusion-exclusion principle but I can't get the correct answer. My code

    private static void solve(long n, long m, long a, long d) {
        long[] values = new long[5];

        for (int i = 0; i < 5; i++) {
            values[i] = a + i*d;
        }

        long left, right, sum = 0, diff = m-n+1;

        for (int i = 0; i < (2 << 5); i++) {
            int count = 0;
            long divisor = 1;
            for (int j = 0; j < 5; j++) {
                if ((i & (1 << j)) > 0) {
                    count++;
                    divisor = lcm(divisor, values[j]);
                }
            }
            left = (n-1)/divisor;
            right = m/divisor;
            if (count % 2 == 0) sum -= right-left;
            else sum += right - left;
        }
        System.out.println(diff-sum);
    }

    private static long lcm(long a, long b) {
        return (a*b)/gcd(a,b);
    }

    private static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
Tags #math, inclusion-exclusion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English __zac__ 2020-07-30 17:44:28 2 Tiny change: '= 0; i < (2 << 5); i+' -> '= 0; i < (1 << 5); i+'
en2 English __zac__ 2020-07-30 17:43:02 234
en1 English __zac__ 2020-07-30 12:23:01 973 Initial revision (published)