글 읽기 - 왜 고대사람들은 자기들도 못푸는걸 문제로 만들었을까요

chminoo 4년 전 0

화나넹

암튼 질문은 다음과 같습니다

이문제가 결론적으로 요구하는건

1 <= x <= n 인 n^2의 약수 x의 개수를 구하는 문제인데

전수탐색으로는 역시 시간초과가 납니다

n이 10억까지 가니까...

처음에 생각했던건

n^2를 소인수 분해 해서 약수의 개수를 구하고 (약수의갯수-1)/2+1 하는 거였는데

생각해보니 소인수 분해가 더 오래걸리겠더라고요 특히 10억^2 범위안에 소수걸리면 끝이니까

그래서 저런식으로 바꿔서 생각해봤는데 저기서 진전이 없습니다

도와주세요~~

import sys


for i in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    print("Scenario #%d:"%(i+1))
    chk = n**2
    result = 0
    for j in range(1, n+1):
        if chk % j == 0:
            result += 1
    print(result)
    print()

ho94949 4년 전 0

n을 소인수 분해 한 결과로 n^2의 소인수 분해를 구하는 방법은 없을까요?

chminoo 4년 전 0

아이고 감사합니다

마침 그렇게 새로 생각해서 풀어서 맞췄는데 답변주셨네요 ㅋㅋㅋ

n을 소인수분해해서 갯수를 구할때 2를 곱해주는식으로 맞췄습니다. 답변감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 고대사람들은 자기들도 못푸는걸 문제로 만들었을까요

chminoo 4년 전 0

ho94949 4년 전 0

chminoo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말