题目描述 该题为「Fermat-1」的 Special Judge。 很有实力的 zyh 又出了一道「费马与定理」。 给定两个正整数 d,n,满足 d,n≤2.5×10 5 ,问是否有 d 是n!+1 的次小约数。 输入格式 本题多测。 第一行,一个正整数 T,表示数据组数。 随后输入 T 组数据。对于每组数据,输入两个正整数d,n,其意义如题目中所描述。 输出格式 对于每组数据,若 d 是 n!+1 的次小约数,则输出 Yes;否则输出 No。(c++代码)
时间: 2024-04-09 09:31:03 浏览: 74
费马大定理:生成费马数,输入“help fermat”。-matlab开发
对于每组数据,我们需要判断是否存在一个数 d,它是 n!+1 的次小约数。我们可以通过计算 n!+1 的所有约数,并找出其中次小的约数来判断。
首先,我们可以使用一个循环来计算 n! 的值。然后,我们可以使用另一个循环来遍历所有可能的约数,并检查它是否满足条件。
以下是实现该功能的 C++ 代码:
```cpp
#include <iostream>
using namespace std;
// 计算 n! 的值
long long factorial(int n) {
long long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
// 判断 d 是否是 n!+1 的次小约数
bool isSecondSmallestDivisor(int d, int n) {
long long num = factorial(n) + 1;
for (int i = 2; i <= num / 2; i++) {
if (num % i == 0) {
if (d == i) {
return true;
}
break;
}
}
return false;
}
int main() {
int T;
cin >> T;
while (T--) {
int d, n;
cin >> d >> n;
if (isSecondSmallestDivisor(d, n)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
```
请注意,上述代码使用了 long long 类型来存储 n! 的结果,以避免溢出。
阅读全文