A5945 | 「2020-2021 集训队作业」function
时间限制2s
内存限制512MB
通过 / 提交0/0
题目描述
定义 $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}$ | |
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?