#509. 「LibreOJ NOI Round #1」动态几何问题

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

题目描述

一天,神犇醒来时发现他的面前摆着一张初中数学试卷 …… 上面是这样一道题:

22.如图,已知两圆相交,作过两圆圆心的直线与两圆依次交于点 W,X,Y,ZW,X,Y,Z,过 XX 作直线 XKXK 垂直于 WZWZ 交圆 WKYWKY 于点 KK,过 YY 作直线 YLYL 垂直于 WZWZ 交圆 XLZXLZ 于点 LL,且 KKLL 在直线的异侧。以 KLKL 为一边作正方形 KLCDKLCD

D.png

(1).已知 XY=1XY=1SKLCDS_{KLCD} 为整数;设 WX=a,YZ=bWX=a,YZ=b,若 a,ba,b 都是整数且 a[1,N],b[1,M]a\in[1,N],b\in[1,M],则有序数对 (a,b)(a,b) 共有多少种可能的取值?

神犇自然是秒了这道题。然而他发现不远处有一名抓耳挠腮丝毫不会的学生,看了十几分钟后神犇终于忍不住了,站起来大喊:

你怎么这么菜啊?我来告诉你:由圆的性质显然可得 KX=a,YL=bKX=\sqrt a,YL=\sqrt b ……

但话还没说完,他就被监考老师拦住了,飒然惊觉的神犇才发现这是一场梦,只留下梦中的你在一脸苦闷地做着题。

输入格式

一行两个正整数 NNMM

输出格式

一行一个正整数,表示满足要求的有序整数对 (a,b)(a,b) 的种数。

样例

样例输入 1

2 2

样例输出 1

2

样例输入 2

77777 66666

样例输出 2

495197

样例输入 3

1000000000 1000000000

样例输出 3

12735999860

数据范围与提示

对于100%100\%的数据,1N,M1.510161 \le N,M \le 1.5*10^{16}

SKLCDS_{KLCD} 表示正方形 KLCDKLCD 的面积。

Subtask # 分值 NN MM
1 33 1\le 1 1015\le 10^{15}
2 55 5000\le 5000 5000\le 5000
3 77 105\le 10^5 105\le 10^5
4 33 106\le 10^6 106\le 10^6
5 1212 107\le 10^7 109\le 10^9
6 99 109\le 10^9 109\le 10^9
7 1111 1011\le 10^{11} 1011\le 10^{11}
8 1010 1013\le 10^{13} 1013\le 10^{13}
9 1010 1015\le 10^{15} 1015\le 10^{15}
10 88 1013\le 10^{13} 5×1015\le 5 \times 10^{15}
11 1717 3×1015\le 3\times 10^{15} 3×1015\le 3\times 10^{15}
12 55 1.5×1016\le 1.5\times 10^{16} 1.5×1016\le 1.5\times 10^{16}