글 읽기 - 살려주세요

lkyxbar 1년 전 0

일단 97, 1031은 소수니깐 뤼카의 정리를 이용해 나머지를 구했습니다 그리고 crt에서 역원을 구하고 그대로 해를 출력했습니다 근데 기다린건 시간 초과 였습니다 살려주세요

import math
import sys
input=sys.stdin.readline
def lucas(n, k, m):
    mod=1

    while n or k:
        a=n%m
        b=k%m
        if a<b:
            mod*=0
            return mod
        else:
            mod*=math.comb(a, b)
        n//=m
        k//=m
    return mod

def powop(a, p, mo):
    rst=1
    while p:
        if p&1:
            rst*=a
            rst%=mo
        a*=a
        a%=mo
        p>>=1
    return rst

def crt(r1, m1, r2, m2):
    a1=powop(m2%m1, m1-2, m1)
    a2=powop(m1%m2, m2-2, m2)
    return (r1*m2*a1+r2*m1*a2)%(m1*m2)

T=int(input())
for _ in range(T):
    N, M=map(int, input().split())
    p, q=97, 1031
    print(crt(lucas(N-1, M-2, p), p, lucas(N-1, M-2, q), q))

lkyxbar 1년 전 0

자문자답합니다 n=0일때에서 시간초과가 발생합니다 n=0, m=1일때 답은 1, n=0, m!=1일때 0입니다

어우 겨우 살아돌아 왔네요;;;

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

문제

문제

출처

ICPC

살려주세요

lkyxbar 1년 전 0

lkyxbar 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말