题意:给你m,a,b,要求输出这样的p和q满足:p、q为素数,a/b<=p/q<=1,p*q<=m且p*q是最大的。
思路:先筛素数,然后找满足这样的p和q。思路很简单,但找的时候注意技巧,一开始TLE了两发。
#include<iostream> #include<cstdio> using namespace std; int s[100000],m,a,b,p,q,num; bool f[100010]; int main() { num=0; for(int i=2;i<=100000;i++) { if(f[i]==0) { s[num++]=i; for(int j=2*i;j<=100000;j+=i)f[j]=1; } } while(scanf("%d%d%d",&m,&a,&b)) { if(m==0&&a==0&&b==0)return 0; p=0; q=0; for(int i=0;;i++) { if(s[i]*s[i]>m)break; for(int j=i;;j++) { if(s[i]*b<s[j]*a||s[i]*s[j]>m)break; if(s[i]*s[j]>p*q) { p=s[i]; q=s[j]; } } } cout<<p<<" "<<q<<endl; } }