Anti division

AtCoderの勉強をしようと思っていたら、
数学的問題を解けた方が良いとのことで以下の問題が進められていたのでやってみました。

atcoder.jp

問題文は単純で以下の通りです。

A ≦ Bの範囲の値で、
CまたはDで割り切れない数がいくつあるかを求める問題です。

一瞬 A ≦ Bの範囲をループ処理することを考慮しましたが、
10^18まで発生する可能性があるので、TLEになると思い別の方法を検討することが大事です。

まず、以下の通り分けて考えました。
①B - Aが、割り切れない可能性がある最大の数
②B - A の数を C で割った数 を求める
③B - A の数をDで割った数を求める

最後に、①に②、③を引けば求められる。。。と思ったのですがこれではまだ不十分です。
ＣとDの割った数が重複している場合、その値は割り切れる数として重複カウントしてしまいます。
この数値は重複せずにカウントする必要があるので、最小公倍数を求めたうえで以下を求める必要があります。
④ B - Aの数をlcm(c, d)で割った数を求める　

lcmとは

lcmとは Least Common Multipleの略で最小公倍数を指します。
最小公倍数はプログラムで表現すると以下の通りとなります。

■アルゴリズム

	static long lcm (long a,long b) {
		long temp;
		long c = a;
		c *= b;  //暫定的にA, Bを掛けた値を設定する。
		while((temp = a%b)!=0) {  //A mod Bを求める。これを繰り返す(ユークリッドの互除法?）によって最終的に求められるっぽい
			a = b;
			b = temp;
		}
		return c/b;
	}

自分でコーディングすると以下の通りとなりました。
一応sampl1～3まではOKでしたが4以降は分からないですね。
■私的回答コード

import java.util.Scanner;

public class Main131_01 {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			long A = scn.nextLong();
			long B = scn.nextLong();
			long C = scn.nextLong();
			long D = scn.nextLong();

			long minmaxVal = B - A + 1;
			long cd = lcm(C, D);
			long div = B / cd - ((A - 1) / cd);
			long cDiv = (A - 1) / C - B / C;
			long dDiv = (A - 1) / D - B / D;

			System.out.println(minmaxVal + div + cDiv + dDiv);

		}
	}

	static long lcm (long a,long b) {
		long temp;
		long c = a;
		c *= b;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return c/b;
	}
}

もうちょっときれいにできると思いますが、こんなところです。
lcmのようなメソッドは良く使うのでatcoderで提出用のソースコードにテンプレで含めておこうかな。。。