題目
本題要求你在給定區間 [a,b] 內找出使得 n?2?? +1 整除 n! 的所有正整數 n，
輸入格式:
輸入在一行中給出兩個正整數 0<a<b≤10?4?? ，其中 (b?a) ≤ 20，
輸出格式:
按照遞增順序，每行輸出一個滿足題面條件的 n，如果解不存在，則輸出 None，
輸入樣例1:
30 50
輸出樣例1:
38
43
47
輸入樣例2:
50 55
輸出樣例2:
None
思路:
借鑒了知乎大佬 @蒼星石 的思路（我是辣雞）：
“不能把階乘算出來！可以用階乘的元素把除數同除，消成1；最后判斷除數（n?2?? +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
放一張令人開心的圖~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/243928.html
標籤：其他