ACM-ICPC 상 탈 사람

문제: icpc.me/13212 1)주어지는 수의 1을 제외한 소인수가 모두 K보다 크면서 2)연속되는 같은 숫자가 4개 이상이 아닌지 확인하는 문제이다. 2)의 조건은 10으로 나눠주면서 연속되는 자리수의 개수를 세주면 되고 1)의 조건은 sqrt(maxNumber)보다 작은 모든 소수를 구해준 뒤 그 수들로 나눠지는 가장 작은 수가 K보다 큰지 여부를 확인해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include using namespace std;typedef long long ll;ll n, k, num;bool p[100010];vecto..

문제: icpc.me/1837 P가 너무 크기 때문에 K를 이용하여 답을 구해내야 한다. 우선 K이하의 소수를 에라토스테네스의 체를 이용하여 구해준 뒤 P가 해당 소수들 중 하나라도 나누어 떨어지는 수가 있다면 BAD를 출력하게 된다. 12345678910111213141516171819202122232425262728293031#include #include using namespace std;char a[110];int k, p[2000000];bool chk(const char *s, int p) { int ret = 0; for (int i = 0; s[i]; i++) ret = (ret * 10 + s[i] - '0') % p; return !ret ? true : false;}int main(..

문제:icpc.me/1747 N보다 큰 수 중에서 소수이면서 팰린드롬인 가장 작은 수를 구하는 문제이다. 에라토스테네스의 체를 이용하여 소수들을 구해놓은 뒤 N보다 큰 수 중에서 팰린드롬인지 검사해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include using namespace std;bool p[2000001];int n;bool ck(int *a, int lo, int hi) { if (lo >= hi)return 1; if (a[lo] != a[hi])return 0; return ck(a, lo + 1, hi - 1);}bool chk(int x) { int c = -1; int a[8]; wh..

문제: icpc.me/1017 N개의 수가 주어질 때 주어진 모든 수를 짝을 지을 때 모든 각각의 짝의 합이 소수가 되도록 할 때 첫 번째 수와 매칭 될 수 있는 모든 수를 구하는 문제이다. 어떤 수 a와 b가 서로 다를 경우 a+b가 소수가 되기 위해서는 a와 b가 짝수와 홀수로 나누어져야한다. 즉 우리는 짝수와 홀수로 이분 그래프 형태로 그래프를 모델링 해준 후 이분 매칭을 구해주어 n/2만큼 매칭 될 경우 1번 정점과 매칭 된 정점을 역추적 해주어 답에 넣어준 후 그 간선만 제거하고 다시 이분매칭을 실행함을 반복해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535..

문제: icpc.me/14431 마을의 좌표가 주어질 때 두 좌표사이의 거리의 정수부분이 소수일 경우에만 이동가능한다는 조건하에 소수마을에서 A마을로 이동하는데 걸리는 최단경로를 구하는 문제이다. 에라토스테네스의 체를 이용하여 소수들을 구해준 후 거리가 소수인 정점들을 서로 간선 연결을 해준 뒤 다익스트라를 돌려서 해결하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include #include #include #include using namespace std;int getdist(pair a, pair b) { return sqrt((a.fir..

문제: icpc.me/4948 n~2n 사이의 소수의 개수를 출력하면 되는 문제이다. 에라토스테네스의 체로 소수들을 구해 준 뒤 파셜섬의 차를 구해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;bool p[270000];int s[270000];int n;int main() { p[0] = p[1] = true; for (int i = 2; i