C - すぬけそだて――ごはん――
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
目当ての「マタタビ」を手に入れたあなたは、「すぬけそだて」を本格的に遊び始めました。
都市の道端とはいえやはり自然は弱肉強食の世界で、拾われたばかりのすぬけ君は弱りきっていました。 あなたは、ゲーム内アイテムを食べさせてあげることで、すぬけ君の体力を回復させようとしています。
さて、すぬけ君は好物が整数の書かれたカードであるという変わったねこです。カードをすぬけ君に与えると、あなたはむしゃむしゃと幸せそうにカードを食べるすぬけ君の愛らしい姿を眺めることができます。 しかし、カードを与えているうちに、あなたはカードを食べてもすぬけ君が喜ばないことがあることに気付きました。また、以下の性質を発見しました。
- すぬけ君は、その日にこれまでに食べたどのカードに書かれた整数とも互いに素である整数の書かれたカードを食べたとき、喜ぶ。そうでないとき、悲しむ。
今日のカードショップには A 以上 B 以下の整数の書かれたカードが 1 枚ずつ売られています。 あなたは、このうちの 0 枚以上の任意の枚数を購入し、すべてのカードをすぬけ君に与えることにしました。このとき、すぬけ君を 1 度でも悲しませてはいけません。
カードの買い方は何通りあるでしょうか。
制約
- 1 \leq A \leq B \leq 10^{18}
- B-A\leq 35
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
カードの買い方の個数を出力せよ。
入力例 1
2 4
出力例 1
6
2 の書かれたカードと 4 の書かれたカードを同時に含まないものすべてが条件を満たします。これは 6 通りあります。
入力例 2
5 9
出力例 2
20
入力例 3
123456789987654321 123456789987654356
出力例 3
105728