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

ID: 1387

传统题

2000ms

512MiB

难度: (无)

上传者:

标签>

数论

2020

2021

题目描述

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

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

输入格式

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

输出格式

输出一个数，表示答案。

10 0

100000000 242

数据范围与提示

对于 $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}$	$\ge 200$
$13$	$\le 10^{10}$	$=0$
$14$	$\le 2\times 10^{10}$	$=0$
$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\times10^{10}$