사용자 도구

사이트 도구


ps:problems:boj:1457

정확해

ps
링크https://www.acmicpc.net/problem/1457
출처BOJ
문제 번호1457
문제명정확해
레벨골드 1
분류

수학

시간복잡도O(sqrt(A+B))
인풋사이즈A<10^6, B<10^7
사용한 언어Python
제출기록31312KB / 72ms
최고기록64ms
해결날짜2021/06/10

풀이

  • 번역이 살짝 헷갈린다. 제대로 다시 정리하면, K<M이고, K∣M 이고, K^N∤M 의 세 조건을 모두 만족하면 K는 M의 멋진 약수이다.
  • f(X) = d(1) + d(2) + … d(X)을 계산하면, 최종 답은 f(A+B) - f(A-1)로 구할 수 있다.
  • f(X)는 1~X 까지의 모든 수의 약수의 갯수의 합을 먼저 구하고, 약수이지만 멋진 약수가 아닌 수의 갯수를 빼주면 된다.
  • 모든 수의 약수의 갯수의 합은 ∑f(x) 계산에 설명된 방식으로 O(sqrt(X))에 계산 가능
  • 약수이지만 멋진 약수가 아닌 수의 갯수의 합은,
    • K^N∤M 을 만족하지 않는 약수의 갯수의 합 = 모든 1~X까지의 K에 대해서 K^N 을 약수로 갖는 M의 갯수의 합 = [X/(1^N)] + [X/(2^N)] + [X/(X^N)]
      • K^N ≤ X일때까지만 계산하면 되니까 실질적으로 계산해야할 텀의 갯수는 O(X^(1/N))개라서 일일이 계산해도 O(X^(1/N))에 해결된다
    • K<M을 만족하지 않는 약수의 갯수의 합 = X개
    • 두가지를 동시에 만족하는 약수의 갯수 = 1개 (X=1일때, K=1)
  • 따라서 f(X) = ∑τ(x) - (X/(1^N)] + [X/(2^N)] + [X/(X^N)]) - X + 1 로 O(sqrt(X))에 계산 가능하다.
  • 최종 답인 f(A+B) - f(A-1) 를 계산하는 것도 O(sqrt(A+B))로 계산되다.

코드

"""Solution code for "BOJ 1457. 정확해".

- Problem link: https://www.acmicpc.net/problem/1457
- Solution link: http://www.teferi.net/ps/problems/boj/1457
"""

import math


def sigma_d(num, exp):
    if num == 0:
        return 0
    sqrt = math.isqrt(num)
    answer = 2 * sum(num // i for i in range(1, sqrt + 1)) - sqrt * sqrt
    i = 1
    while (x := i**exp) <= num:
        answer -= num // x
        i += 1
    answer -= num - 1
    return answer


def main():
    A, B, N = [int(x) for x in input().split()]
    print(sigma_d(A + B, N) - sigma_d(A - 1, N))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
D K V U A
 
ps/problems/boj/1457.txt · 마지막으로 수정됨: 2021/06/10 03:56 저자 teferi