1136 - Substring of Extension FizzBuzz

問題

自明 証明したり特に詳しく説明したりするまでもなく明らかなこと。

FizzBuzzとは、 有る値Nが3で割り切れるとき"Fizz"を、5で割り切れるとき"Buzz"を、双方で割り切れるときは"FizzBuzz"を言うものである。
割り切れない場合はNそのものを言う。
なお、「割り切れる」は任意の正整数の除数aと被除数b、余りを出す演算子%で表現した時b%a==0となることを言う。
0で除算した場合は「割り切れない」とする。
例えば、3や12は"Fizz"と、5や550は"Buzz"と、15や45は"FizzBuzz"と出力する。
これを、1からXまで繰り返す。それが本来のFizzBuzzである。
ここではFizzBuzzを少し拡張し、Aで割り切れたらFizzを、Bで割り切れたらBuzzを、双方で割り切れるときは"FizzBuzz"を言うものとする。

さて、X=10¹⁰⁰⁰として、値ごとに改行をしないものとする。
そうすると、もしA=3、B=5であれば"12Fizz4BuzzFizz78FizzBuzz11Fizz1314FizzBuzz..."という文字列が完成する。
完成した文字列にそれぞれ番号をつけるが、例の文字列であれば最初から順番に、"1"には番号1を、"2"には2を、"Fizz"には3を、"4"には4を、"Buzz"には5を、"6"には6と番号を付ける。もちろん、最初の"FizzBuzz"という文字列は15番が与えられる。
この時値$L$と$R$の2つを決めたとき、番号$L$から番号$R$までの拡張FizzBuzzを行ったときの文字列長を答えよ。

入力

1行目にA、Bが空白区切りで与えられる
2行目にL、Rが空白区切りで与えられる

出力

$L$から$R$までの文字列長を1行で答えよ。
各行の改行を忘れずに。

制約

• 0 ≤ $A$,$B$ ≤ 10⁶
• 1 ≤ $L$ ≤ $R$ ≤ 10¹⁶

小課題

1. (5 点) $A$,$B$ = $1$, $L$,$R$ ≦ $10$^$7$
2. (5 点) $L$,$R$ ≦ $10$^$7$
3. (20 点) 追加の制約はない.

入出力例

例1

入力

3 5
1 20

出力

57

これは、通常のFizzBuzzを20まで行ったときの文字列長である。
12Fizz4BuzzFizz78FizzBuzz11Fizz1314FizzBuzz1617Fizz19Buzz
となるため、57と出力すればACする。
なお、57は素数である。

例2

入力

8 1
6 19

出力

64

A=8の倍数のときに"Fizz"、B=1の倍数のときに"Buzz"になるため、このテストケースで生成される文字列に数字は含まれない。
6番目から開始するため、以下の様に最初から3つ目に"Fizz"があらわれ、かつBの倍数でもあるために"Buzz"もあらわれる。
"BuzzBuzzFizzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzFizzBuzzBuzzBuzzBuzz"という文字列が生成されるため、64を出力する。

例3

入力

0 1
10 100

出力

364

BuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzzBuzz