pseong

백준 1557 제곱 ㄴㄴ 본문

알고리즘/알고리즘 문제풀이

백준 1557 제곱 ㄴㄴ

pseong 2022. 12. 6. 23:04

제곱수로 나누어 떨어지는 경우 이미 처리해 줬기 때문에 제곱수로 안 나누어 떨어지는 경우에 대해서만 포함 배제의 원리를 사용해야 한다.

 

제곱수로 나누어 떨어지는 경우는 전부 계산에서 제외해 주었기 때문에 어떤 수의 소인수들은 전부 한개만 가지고 있다.

 

먼저 x까지의 모든 숫자의 개수는 x개이다.

소수인수가 홀수개로 이루어져 있다면 빼주면 되고 짝수개로 이루어져 있다면 더해주면 된다.

 

1557번: 제곱 ㄴㄴ

어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K

www.acmicpc.net

 

'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글

Hello 2023  (2) 2023.01.04
Good Bye 2022: 2023 is NEAR  (0) 2023.01.04
Educational Codeforces Round 121 (Rated for Div. 2) D. Martial Arts Tournament  (0) 2022.07.28
Codeforces Global Round 17 D. Not Quite Lee  (0) 2022.06.30
Educational Codeforces Round 117 (Rated for Div. 2) E. Messages  (0) 2022.06.27
'알고리즘/알고리즘 문제풀이' Related Articles more
Comments