#1274. 「X Round 2」记忆

内存限制:512 MiB 时间限制:1200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wjyyy

题目描述

过去就像攥在手中的一把干沙,自以为攥得很紧,其实早就从指缝中流光了。记忆是一条早已干涸的河流,只在毫无生气的河床中剩下零落的砾石。——刘慈欣 《三体》


你的记忆被歌者拿走了。

临走前,歌者告诉你,你的记忆中有一个序列,而且这个序列是所有 l \le x \le r 的整数 x 形成的一个排列。

歌者想了想,决定再告诉你一点信息:

如果把一个序列的权值定义为这个序列中相邻两个数的乘积为完全平方数的数量,那么你记忆中的这个序列是所有 l \le x \le r 的整数 x 形成的排列中权值最大的排列。

歌者希望你能够把你记忆中的这个序列的权值告诉他,他才会把属于你的记忆还给你。

输入格式

一行两个正整数 l,r

输出格式

一行一个整数,表示答案。

样例

样例 1 输入

2 10

样例 1 输出

2

样例 1 说明

一个满足权值为 2 的排列为 \{8,2,4,9,3,10,7,5,6\} ,其中 8 \times 2 = 16, 4 \times 9=36 为完全平方数。这也是所有 2 \le x \le 10 的整数 x 形成的排列中权值最大的排列。

数据范围与提示

本题采用捆绑测试。

Subtask 1(3 points): r \le 10
Subtask 2(7 points): r \le 100
Subtask 3(15 points): r \le 100000
Subtask 4(11 points): l = 1
Subtask 5(8 points): l \le 10
Subtask 6(19 points): l \le 1000000
Subtask 7(37 points):无特殊限制。

对于 100\% 的数据, 1 \le l \le r \le 10^{14}

命题人:meaningful