a-贝利福斯数

[编程题]a-贝利福斯数

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将所有形如ax+1的数称为a-贝利福斯数，其中x是正整数。
一个a-贝利福斯数是a-贝利福斯素数，当且仅当它不能被分解成两个a-贝利福斯数的积。
现在给出a,n，问有多少个 ≤ n的a-贝利福斯数可以被分解成两个a-贝利福斯素数的积。

输入描述:

一行两个数a,n

输出描述:

一行一个数表示答案

示例1

输入

4 25

输出

说明

≤ 25 的 4-贝利福斯数有5,9,13,17,21,25。
其中4-贝利福斯素数有5,9,13,17,21，
可以被分解成两个a-贝利福斯素数的积只有25。

备注:

1 ≤ a ≤ 10,1 ≤ n ≤ 2 x 10⁷ x a

算法知识视频讲解

耕云种月

发表于 2022-07-10 20:27:15

原题解链接：https://ac.nowcoder.com/discuss/149978 考虑使用类似线性筛的方法，从小到大枚举每个a-贝利福斯数 iii ，然后从小到达枚举每个a-贝利福斯素数 xxx ，标记 i×xi \times xi×x ，如果 i mod x=0i \bmod x=0imo 展开全文