Coprime Present

题目描述

你有 $B-A+1$ 张卡片：对于从 $A$ 到 $B$ 的每个整数，你有一张写有该整数的卡片。 你会把其中一些（也可能一个都不给）给你的宠物 Snuke。 如果对于每一对不同的卡片，上面写的数字两两互质，Snuke 就会高兴；否则，他会难过。 有多少个卡片集合会让 Snuke 高兴？

输入格式

输入从标准输入按以下格式给出： $A$ $B$

输出格式

输出会让 Snuke 高兴的卡片集合的数量。 题目保证答案小于 $2^{63}$。

2 4

6

1 1

2

123456789000 123456789050

2125824

提示

$1 \leq A \leq B \leq 10^{18}$ $B-A \leq 72$ 输入中的所有值都是整数。你有三张写着 $2$、$3$ 和 $4$ 的卡片。以下六个卡片集合会让 Snuke 高兴：

$\{\}$ $\{2\}$ $\{3\}$ $\{4\}$ $\{2,3\}$ $\{3,4\}$
以下两个卡片集合会让 Snuke 高兴：

$\{\}$ $\{1\}$

标签: AtCoder|abc195F

来源

AtCoder|abc195F