-
[PS] 백준 1016번: 제곱 ㄴㄴ 수문제해결 2023. 11. 9. 03:38
공부하다 옆 친구가 풀고 있었는데, 최근에 풀었던 문제랑 비슷해서 바로 눈길이 가서 풀어보았다.
분수 찾기 문제를 최근에 풀었기에 바로 생각이 났는데
int find_pos(int a, int b) { int ret = 0; for(int i = 1; i <= N; i++) arr[i] = a * i / b; for(int i = 1; i <= N; i++) { ret += arr[i]; for(int j = i * 2; j <= N; j += i) { arr[j] -= arr[i]; } } return ret; }
이 방식으로 4의 배수인 4, 8, 12, 16, ... 전부다 체크해두고
다음엔 9의 배수인 9, 18, 27, ... 다 체크해두고를 반복하다
마지막에 체크 안된 애들의 개수를 세는 방식으로 풀었다.
#include <bits/stdc++.h> using namespace std; #define FOR(i, n) for(int i = 0; i < int(n); i++) #define FORL(e, s) for(auto &e : s) #define endl "\n" int arr[1'000'001]; int main() { long long firstnum, lastnum; cin >> firstnum >> lastnum; long long len = lastnum - firstnum + 1; for (long long i = 2; i * i <= lastnum; i++) { long long i2 = i * i; long long startpos = (firstnum / i2 + bool(firstnum % i2)) * i2; for (long long j = startpos - firstnum; j < len; j += i2) { arr[j] = 1; } } int cnt = 0; FOR(i, len) { if (arr[i] == 0) cnt += 1; } cout << cnt << endl; return 0; }
'문제해결' 카테고리의 다른 글
[PS] 백준 11689번: GCD(n, k) = 1 (1) 2023.11.20 [PS] 백준 17390번: 이건 꼭 풀어야 해! (입출력 관련) (1) 2023.11.09 [PS] 백준 1882번: 분수 찾기, 30449번: Reafy 수열 (0) 2023.11.07 [PS] 백준 13908번: 비밀번호 (1) 2023.11.02 [PS] 백준 16455번: K번째 수 찾는 함수 (1) 2023.11.01