[editorial] 9월 20일 모의고사 에디토리얼 (F번)

  • User Avatar
    astein

    F - Factorial [문제링크]
    n! 을 b 진수로 표현했을 때 뒤에 0이 몇 개나 붙는지를 세는 문제입니다.
    만약, b가 소수(prime number)라면 n! 에 b 가 몇 번이나 곱해져 있는지만 counting 하면 됩니다. :-D 하지만 b가 합성수(composite number)인 경우, b를 인수분해 하여 각각의 인수들이 몇 번씩 곱해져 있는지를 counting 해 줘야 합니다.
    b = a1p1 * a2p2 * ... * akpk (a1, a2, ..., ak = prime number, p1, p2, .., pk > 0) 이라고 합시다.
    n!에 어떤 소수 ai 가 몇 번 곱해져 있는지를 counting하는 알고리즘은 아래와 같습니다.
    [spoiler="더 보기..."] ai의 계수 = n / ai + n / ai2 + n / ai3 + ...
    [/spoiler]
    만약에 b를 인수분해 했을때 2가 3번 곱해져 있고 n!에 2가 97번 곱해져 있다고 가정하면, 이 경우 n!에 0이 최대한 많이 들어간다고 하면 97 / 3 = 32.xxx = 32번까지 사용 가능합니다. 모든 소수에 대하여 위의 과정을 반복하면 0이 몇 개나 나오는지 셀 수 있습니다.
    --- (설명이 부족한 듯 싶은데, 댓글로 달아주시면 추가해 드리겠습니다.) ---

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    18년 전
4개의 댓글이 있습니다.
  • User Avatar
    hyunhwan

    http://acm.pku.edu.cn/JudgeOnline/problem?id=1401 엮임문제로 하나 추가 'ㅅ' 덕분에 한문제 풀었어용 감사감사


    18년 전 link
  • User Avatar
    @,.@

    "ai의 계수 = n / ai + n / ai2 + n / ai3 + ..." 관련된 레퍼런스를 알려주실수 없나요?? 이해가 안되네요..@,.@


    18년 전 link
  • User Avatar
    JongMan

    어떤 숫자 k 를 2로 n번 나눌 수 있다고 합시다. 그러면 k 는 2n 의 배수겠죠.
    ai 중에 2의 배수가 몇 개나 있을까요? ai/2 개 있겠죠.
    ai 중에 22의 배수는 ai/(22) 개 있을 테고..
    23 의 배수는 ai/(23) 개 있을 테죠.
    이들의 수를 다 더하면, 23 의 배수들은 22 의 배수 셀때도 카운트 되고 21 의 배수 셀 때도 카운트 되니 3번 카운트 되고..
    모든 2n 의 배수들 (최대 2n 이라는 얘깁니다.. 2n+1 의 배수가 아닌) 은 n번씩 카운트 되겠죠. ^


    18년 전 link
  • User Avatar
    @,.@

    감사합니다..ㅋㅋ


    18년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.