Write a function which calculates the sum of all natural numbers under n (first argument) which are evenly divisible by at least one of a and b (second and third argument). Numbers a and b are guaranteed to be coprimes.

Note: Some test cases have a very large n, so the most obvious solution will exceed the time limit.

(ns live.test
  (:require [cljs.test :refer-macros [deftest is run-tests]]))

;; jafingerhut's solution:

;; The trick to calculating the answer very quickly is knowing a few
;; math facts.
 
;; 1. The sum of all numbers from 1 through n, inclusive, is
;;    n*(n+1)/2.  See Wikipeda article on Arithmetic Progression for
;;    one proof of this (in a more general form).
 
;; 2. The sum of all numbers that evenly divide a that are less than n
;;    is:
;;        a + 2*a + 3*a + ... + k*a
;;    where k is largest integer such that k*a < n, which is
;;    floor((n-1)/a), or (quot (dec n) a).  By factoring out a, we can
;;    see this is equal to:
;;        a * (1 + 2 + 3 + ... + k)
;;    By fact 1, this is equal to:
;;        a * k * (k+1) / 2
 
;; 3. Numbers less than n that are evenly divisible by at least one of
;;    a and b are:
;;        divisible by a: a + 2*a + 3*a + ... + k*a
;;        divisible by b: b + 2*b + 3*b + ... + l*b     where l=(quot (dec n) b)
;;    We can use fact 2 to easily calculate these two sums, but that
;;    would double-count all of these numbers:
;;        divisible by a*b: a*b + 2*a*b + 3*a*b + ... + m*a*b
;;    We know those are the only numbers double-counted, because we
;;    are told that a and b are coprime.  Fortunately it is easy to
;;    calculate that sum and subtract it out.
 
(defn big-divide [n a b]
  (let [sum-multiples-of (fn [divisor]
                           (let [x (quot (dec n) divisor)]
                             (/ (*' divisor x (inc x)) 2)))]
    (- (+ (sum-multiples-of a) (sum-multiples-of b))
       (sum-multiples-of (* a b)))))
       
(deftest big-divide-test
  (is (= 0 (big-divide 3 17 11)))
  (is (= 23 (big-divide 10 3 5)))
  (is (= 233168 (big-divide 1000 3 5)))
  (is (= "2333333316666668" (str (big-divide 100000000 3 5))))
  (is (= "110389610389889610389610"
    (str (big-divide (* 10000 10000 10000) 7 11))))
  (is (= "1277732511922987429116"
    (str (big-divide (* 10000 10000 10000) 757 809))))
  (is (= "4530161696788274281"
    (str (big-divide (* 10000 10000 1000) 1597 3571)))))
    
(run-tests)