[BOJ] 17466번: N! mod P(1)

2023. 2. 16. 09:51·Problem Solving/Baekjoon

출처 : https://www.acmicpc.net/problem/17466

 

17466번: N! mod P (1)

양의 정수 N과, N보다 큰 소수 P가 주어질 때, N!을 P로 나눈 나머지를 구하여라.

www.acmicpc.net

 

 

 

1. 문제 설명 

양의 정수 N과, N보다 큰 소수 P가 주어질 때, N!을 P로 나눈 나머지를 구하여라.

 

 


2. 접근 방식 

모듈러 연산 특징을 활용하여 풀었다. 

 

A+B%C = ((A%C) + (B%C)) % C

A-B%C = ((A%C) - (B%C)) % C

A*B%C = ((A%C) * (B%C)) % C

 

언제 공부했더라.. 무튼 기억이 났다 ㅎ......

 

 


3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import sys
input = sys.stdin.readline
n, p = map(int, input().split())
total = 1
for i in range(2, n+1):
    total = (total * i) % p


print(total % p)

 


4. 분석 및 시간복잡도 

1 <= n, p < 10^8

python3은 시초가 떴다. 아무리 n번돌면서 상수 시간의 계산을 한다하더라도 10^8이라 상수시간도 무시못하는 듯하다. pypy로 돌려주자. 

 

 

'Problem Solving/Baekjoon' 카테고리의 다른 글
  • [BOJ] 11723번: 집합
  • [BOJ] 25327번: 다중 항목 선호도 조사(Large)
  • [boj] 14501번: 퇴사
  • [boj] 13975번: 파일 합치기 3
kimdozzi
kimdozzi
끝까지 포기하지 않으면, 내가 다 이겨!
  • kimdozzi
    도브로
    kimdozzi
  • 전체
    오늘
    어제
    • 분류 전체보기 (132)
      • Problem Solving (49)
        • Baekjoon (29)
        • Programmers (0)
        • LeetCode (17)
        • 삼성 유형 (2)
      • Computer Science (27)
        • Operating System (2)
        • Algorithms (13)
        • Network (6)
        • DataBase (6)
      • Backend (33)
        • JavaScript (0)
        • TypeScript (6)
        • Java (7)
        • Spring Boot (7)
        • Spring Security (6)
        • JPA (2)
        • Mybatis (1)
        • Junit5 (1)
        • Redis (3)
      • DevOps (14)
        • Git, Github (5)
        • docker (4)
        • AWS (3)
        • nginx (2)
      • etc (6)
        • IntelliJ (3)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
    • 티스토리
    • 설정
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    CORS
    누적합
    파이썬
    imos법
    점 업데이트
    docker
    docker image
    알고리즘
    오블완
    구간합
    S3
    세그먼트 트리
    python
    백준
    Bucket
    TypeScript
    온라인 쿼리
    AWS
    인덱서블 타입
    PrefixSum
    segment tree
    인터페이스
    티스토리챌린지
    인덱스 시그니처
    오프라인 쿼리
    타입스크립트
    삼성기출
    interface
    도커
    컨테이너
    구간 업데이트
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
kimdozzi
[BOJ] 17466번: N! mod P(1)
상단으로

티스토리툴바