#P8000. [2021年山东省队集训]点整的上圆

    ID: 8013 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-二平方和表示计数Min_25 筛素数计数整除分块线性筛深度优先搜索可行性剪枝

[2021年山东省队集训]点整的上圆

题目描述

整点,就是横纵坐标都为整数的点。现在小猫想问你半径为 RR 的圆周上有多少个整点。

你说,这不是 BZOJ 原题么。

小猫只好把问题反过来。现在已知一个圆,半径为不超过 RR 的正整数,圆周上恰有 NN 个整点,求如此的圆的数量。

输入格式

一行两个整数 R,NR, N。

输出格式

一行一个整数,表示如此的圆的数量。

样例 #1

样例输入 #1

10 4

样例输出 #1

8

样例 #2

样例输入 #2

9876543210 84

样例输出 #2

32581980

提示

对于 10%10\% 数据,保证 R≤1000R ≤ 1000;

对于 30%30\% 数据,保证 R≤107R ≤ 10^7;

对于另外 30%30\% 数据,保证 N≤10N ≤ 10;

所有数据保证 N,R≤1010N, R ≤ 10^{10}。