题目
本题要求你在给定区间 [a,b] 内找出使得 n2 +1 整除 n! 的所有正整数 n。
输入格式:
输入在一行中给出两个正整数 0<a<b≤104 ,其中 (b−a) ≤ 20。
输出格式:
按照递增顺序,每行输出一个满足题面条件的 n。如果解不存在,则输出 None。
输入样例1:
30 50
输出样例1:
38
43
47
输入样例2:
50 55
输出样例2:
None
思路:
借鉴了知乎大佬 @苍星石 的思路(我是辣鸡):
“不能把阶乘算出来!可以用阶乘的元素把除数同除,消成1;最后判断除数(n2 +1)有没有变成1。”
Code: #include<bits/stdc++.h>using namespace std;int main(){int x,y;cin>>x>>y;int count=0;for(int i=x;i<=y;i++){int res=i*i+1;for(int j=1;j<=i;j++){//感谢评论区指正!之前没有考虑到类似于34整除17的情况if(res>=j&&res%j==0&&res!=1) res/=j;else if(res<j&&j%res==0) res=1;}if(res==1){count++;cout<<i<<endl;}}if(count==0) cout<<"None"<<endl;return 0;} AC
放一张令人开心的图~