hdu 1239Calling Extraterrestrial Intelligence Again
1743 ワード
問題は比較的に簡単で、書きやすくて、しかしテストのデータは多くて、TLにやさしいです......
牛のコードを添付して・・・
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int pr[100001]={0};
int prime[50000];
int main()
{
int m, a, b;
int p, q, max, temp;
int i, j, num=0;
double d=sqrt(100000*1.0);
for(i=2; i<=d; i++)//
for(j=2; j*i<=100000; j++)
{
pr[i*j]=1;
}
for(i=2; i<=100000; i++)
{
if(!pr[i])
{
prime[num]=i;
num++;
}
}
while( scanf("%d %d %d", &m, &a, &b) && (m||a||b) )
{
max=0;
d=a*1.0/b;
for(i=0; prime[i]<=m && i<num; i++);// ! , TL……
i--;
for(i; i>=0; i--)
for(j=i; j>=0; j--)
{
temp=prime[i]*prime[j];
if(temp<=m && prime[j]*1.0/prime[i]>=d && temp>max)
{
max=temp; p=prime[j]; q=prime[i];
}
}
printf("%d %d
", p, q);
}
}
牛のコードを添付して・・・
#include <iostream>
#include <cmath>
using namespace std;
#define MAX 100000
int n[MAX];
int main(int argc, char *argv[])
{
int i, j, flag, m1, sq;
int m, a, b;
for(i=0; i<MAX; i++)
n[i] = 1;
n[0] = n[1] = 0;
for(i=2; i<=(int) sqrt(MAX*1.0); i++)
for(j=2; j*i <MAX; j++)
n[i*j] = 0;
while(cin>>m>>a>>b, m||a||b)
{
m1 = m;
flag = 0;
while(m1)
{
sq = (int)sqrt((double)m1);
while(sq >= 2)
{
if(n[sq] && m1%sq == 0 && n[m1/sq] && sq*1.0/(m1/sq) >=a*1.0/b)
{
cout<<sq<<' '<<m1/sq<<endl;
flag = 1;
break;
}
sq--;
}
if(flag) break;
m1--;
}
}
return 0;
}