[낙곡] P1217 [USACO1.5] 회문질수Prime Palindromes(시뮬레이션)
제목 설명
151은 하나의 질수이자 하나의 회문수이기 때문에 151은 회문수이다.
프로그램 하나를 써서 범위 [a, b](5≤a
첫 번째 줄: 두 개의 정수 a와 b.
출력 형식:
회문 질수의 목록을 한 줄씩 출력합니다.출력 샘플 가져오기
샘플 #1 입력:
5 500
샘플 내보내기 #1:
5 7 11 101 131 151 181 191 313 353 373 383 설명
시공 제한: 1000ms, 128M
Hint 1: Generate the palindromes and see if they are prime.
제시1: 모든 회문수를 찾아서 그것들의 질수(소수)를 판단한다.
Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.
힌트2: 정확한 회문수를 만들려면 아래와 같은 순환이 몇 개 필요할 수도 있다.
제목 번역은 NOCOW에서 나왔다.
USACO Training Section 1.5
길이가 5인 회신 수 생성:
for (d1 = 1; d1 <= 9; d1+=2) { //
for (d2 = 0; d2 <= 9; d2++) {
for (d3 = 0; d3 <= 9; d3++) {
palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//( ...)
}
}
}
사고방식: 시뮬레이션 문제, 쉬운TLE를 사용했습니다. 저는 빠른 읽기, 에이치 체질, 그리고 아래 조건에 부합되지 않는 수를 모두 건너뛰었기 때문에 시간이 반으로 줄었고 500여 ms만 필요합니다.
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=9999999;
int prime[N];
inline int read(){ //
char c=getchar();int num=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())
num=num*10+c-'0';
return num;
}
bool digit(int x){ // 11
if((x>=1000&&x<=9999)||(x>=100000&&x<=999999))
return 0;
if(x>=10&&x<=99&&x!=11)
return 0;
return 1;
}
bool huiwen(int x){ //
int y=x,num=0;
while(y)
{
num=num*10+y%10;
y/=10;
}
if(num==x)
return 1;
else
return 0;
}
int main(){
for(int i=0;i<=N;i++) // ， 1， 0
prime[i]=1;
prime[0]=prime[1]=0;
for(int i=2;i<=N;i++){
if(!prime[i])
continue;
for(int j=i*2;j<=N;j+=i)
prime[j]=0;
}
int a,b;
a=read(),b=read();
if(a%2==0) //
a++;
b=min(9999999,b); // 9999999
for(int i=a;i<=b;i+=2){ //
if(!digit(i)) //
continue;
if(!huiwen(i)) //
continue;
if(!prime[i]) //
continue;
printf("%d
",i); //
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
