AT_abc195_f [ABC195F] Coprime Present

题目描述

你有 $B-A+1$ 张卡片，每张卡片上写有一个整数，分别为 $A$ 到 $B$ 之间的所有整数，每个整数各一张。你可以从中选出若干张（也可以一张都不选），打算送给你的宠物すぬけ君。

如果你送出的卡片中，任意两张卡片上所写的数都是互质的，すぬけ君会感到高兴；否则他会感到难过。

请问有多少种卡片的组合方式会让すぬけ君高兴？

输入格式

输入以如下格式从标准输入读入。

$A$ $B$

输出格式

输出让すぬけ君高兴的卡片组合数。在题目的约束条件下，可以证明答案不会超过 $2^{63}$。

样例 1

输入

2 4

输出

6

样例 2

输入

1 1

输出

2

样例 3

输入

123456789000 123456789050

输出

2125824

说明/提示

限制条件

• $1\leq A\leq B\leq 10^{18}$
• $B-A\leq 72$
• 输入均为整数。

样例解释 1

你有写有 $2,3,4$ 的卡片各一张。让すぬけ君高兴的卡片组合有：

• $\{\}$
• $\{2\}$
• $\{3\}$
• $\{4\}$
• $\{2,3\}$
• $\{3,4\}$ 共 $6$ 种。

样例解释 2

让すぬけ君高兴的卡片组合有：

• $\{\}$
• $\{1\}$ 共 $2$ 种。

由 ChatGPT 4.1 翻译