「2020-2021 集训队作业」function - 题目详情 - 柒行

ID: 4641

传统题

1000ms

256MiB

难度: 10

上传者:

标签>

数论

其他

分治

题目描述

定义 $P(x)$ 表示满足 $1 < y < x$ ， $y^3 \equiv 1 \pmod{x}$ 的 $y$ 的数量。

求在 $n$ 以内有多少正整数满足 $P(x) = m$ 。

输入格式

一行输入两个整数 $n, m$ 。

输出格式

输出一个数，表示答案。

样例 1

输入： $10$ $0$
输出： $8$

样例 2

输入： $100000000$ $242$
输出： $24038$

数据范围与提示

对于 $100\%$ 的数据，满足 $1 < n \le 2 \times 10^{10}$ ， $0 \le m < n$ 。

测试点编号	$n$	$m$
$1$	$\le 2 \times 10^{10}$	$= 666$
$2$	$\le 10^3$	-
$3$	$\le 10^5$
$4$	$\le 10^6$
$5$	$\le 3 \times 10^6$
$6$	$\le 5 \times 10^6$
$7$	$\le 10^7$
$8$	$\le 10^8$	$\ge 300$
$9$	$\le 5 \times 10^8$	-
$10$	$\le 10^9$	-
$11$	$\le 5 \times 10^9$	$\ge 200$
$12$	$\le 10^{10}$	-
$13$	-	$= 0$
$14$	$\le 2 \times 10^{10}$	-
$15$	$\le 10^8$
$16$	$\le 5 \times 10^8$
$17$	$\le 10^9$
$18$	$\le 5 \times 10^9$
$19$	$\le 10^{10}$
$20$	$\le 2 \times 10^{10}$