F - Coprime Present Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

あなたは A 以上 B 以下の整数が書かれたカードを各 1 枚、合計 B-A+1 枚持っています。 この中から何枚かを選んで (0 枚でもよい) ペットのすぬけ君にプレゼントしようと考えています。

すぬけ君は、プレゼントされたカードたちについて、どの相異なる 2 枚に書かれた数も互いに素であるときに喜び、そうでないとき悲しみます。

すぬけ君が喜ぶようなカードの組合せは何通りありますか？

制約

  • 1 \leq A \leq B \leq 10^{18}
  • B-A \leq 72
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

A B

出力

すぬけ君が喜ぶようなカードの組合せは何通りあるか出力せよ。 なお、制約の条件下で答えは 2^{63} 未満になることが証明される。

入力例 1

2 4

出力例 1

6

あなたは 2,3,4 が書かれたカードを 1 枚ずつ持っています。すぬけ君が喜ぶようなカードの組合せは

  • \{\}
  • \{2\}
  • \{3\}
  • \{4\}
  • \{2,3\}
  • \{3,4\}

の 6 通りです。

入力例 2

1 1

出力例 2

2

すぬけ君が喜ぶようなカードの組合せは

  • \{\}
  • \{1\}

の 2 通りです。

入力例 3

123456789000 123456789050

出力例 3

2125824

Score : 600 points

Problem Statement

You have B-A+1 cards: for each integer from A through B, you have one card with that integer written on it. You will give some of them (possibly none) to your pet, Snuke.

Snuke will be happy if, for every pair of different cards, the numbers written on them are pairwise coprime; otherwise, he will be sad.

How many sets of cards will make Snuke happy?

Constraints

  • 1 \leq A \leq B \leq 10^{18}
  • B-A \leq 72
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

Print the number of sets of cards that will make Snuke happy. The constraints guarantee that the answer is less than 2^{63}.

Sample Input 1

2 4

Sample Output 1

6

You have three cards with 2, 3, and 4 written on them. The following six sets of cards will make Snuke happy:

  • \{\}
  • \{2\}
  • \{3\}
  • \{4\}
  • \{2,3\}
  • \{3,4\}

Sample Input 2

1 1

Sample Output 2

2

The following two sets of cards will make Snuke happy:

  • \{\}
  • \{1\}

Sample Input 3

123456789000 123456789050

Sample Output 3

2125824