A5945. 「2020-2021 集训队作业」function
编程题
NOI/NOI+/CTSC
知识点
题目描述
定义 $P(x)$ 表示满足 $1< y< x,y^3\equiv 1\pmod x$ 的 $y$ 的数量。
求在 $n$ 以内有多少正整数满足 $P(x)=m$。
求在 $n$ 以内有多少正整数满足 $P(x)=m$。
输入格式
一行输入两个整数 $n,m$。
输出格式
输出一个数，表示答案。
输入输出样例
输入 #1
10 0
输出 #1
8
输入 #2
100000000 242
输出 #2
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$ | $\ge 300$ |
| $10$ | $\le 10^9$ | $\ge 300$ |
| $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}$ | |
| 测试点编号 | $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$ | $\ge 300$ |
| $10$ | $\le 10^9$ | $\ge 300$ |
| $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}$ | |