BOJ 1016: 제곱 ㄴㄴ 수 작성일 2020-02-14 https://www.acmicpc.net/problem/1016 2월동안 187문제 풀기(지난달 누적 87개) (23/187) 3년전에 풀다가 실패한 문제. 이번에는 얼추라도 방법을 생각해내서 풀려고 했으나 –> 사소한 실수로 겁나 뺑이쳤다. 나누어 떨어지면 나머지가 없는 당연한 사실을 알아야 한다. 1234567891011121314151617181920212223#include <bits/stdc++.h> using namespace std; const int SZ = 1000001; typedef long long LL; int visit[SZ]; LL sq[SZ]; int main() { LL a, b, cnt, c = 0; cin >> a >> b; for(LL i = 2; i*i <= b; i++) sq[c++] = (i*i); cnt = b - a + 1; for(int j = 0; j < c; j++) { LL x = sq[j]; LL lb = (a / x) * x + (a % x ? x : 0); for(LL i = lb; i <= b; i += x) if (!visit[i-a]) visit[i-a] = 1, cnt--; } cout << cnt; }