백준 #15897 잘못 구현한 에라토스테네스의 체


BOJ #15897 - 잘못 구현한 에라토스테네스의 체

https://www.acmicpc.net/problem/15897

# 문제 분류

수학, 정수론

풀이 접근 방법


  1. NN = 12나 13 정도 두고 돌려보면 어느정도 규칙을 알 수 있습니다.
  2. 루트 NN 정도까지는 어느정도 계속 변하는 모습을 보여주지만, 그 이후에는 일정한 값을 유지하는 부분이 존재합니다.
  3. NN 제한이 10910^9이기 때문에, 루트 이후에 더 빠르게 처리하는 방법을 고안해야만 합니다.
  4. 일단 바깥 for문이 i번째일 때 몇 번 동작하는가는 ceil(N/i)\text{ceil}(N/ i) 를 이용하면 알 수 있고,
  5. 그 범위가 언제까지 지속되는가는 ceil(N/(ceil(N/i)1))1\text{ceil}(N/(\text{ceil}(N/i)-1))-1 까지 입니다.
  6. 그래서 적절히 for문을 돌려주신 이후에, 마지막은 항상 1이 추가된다는 점을 이용해서 for문을 마쳐주면 됩니다.

개인적으로 굉장히 어려운 문제라고 생각합니다.

특히 몇 번 동작하는지에 대한 식을 세우는 부분이 높은 수학적 직관을 요구하기에..
저는 수학을 잘 못합니다.


#include <iostream>

using namespace std;

int x1, y1, x2, y2, x3, y3;

int cross(int a, int b, int c, int d) {
    return a * d - c * b;
}

int main() {
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

    int result = cross(x2 - x1, x3 - x2, y2 - y1, y3 - y2);
    if (result > 0)
        cout << 1;
    if (result < 0)
        cout << -1;
    if (result == 0)
        cout << 0;
    return 0;
}