C++程序题：可怜的简单题

可怜的简单题九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A: 1 . 最开始，数列 A 为空。 2 . 可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。 3 . 如果不存在一个大于 1 的正整数 w，满足 A 中所有元素都是 w 的倍数，数组 A 将会作为随机生成的结果返回。否则，可怜将会返回第二步，继续增加 A 的长度。现在，可怜告诉了你数列 n 的值，她希望你计算返回的数列 A 的期望长度。时间限制：60000 内存限制：1048576 输入输入一行两个整数 n, p (1 ≤ n ≤ 1011, n < p ≤ 1012)，p 是一个质数。输出在一行中输出一个整数，表示答案对 p 取模的值。具体来说，假设答案的最简分数表示为 x/y，你需要输出最小的非负整数 z 满足 y × z ≡ x mod p。样例输入样例1：

2 998244353

样例2：

100000000 998244353

样例输出样例1：

样例2：

New