- k를 밑으로 하는 소수 자릿수 찾기
문제 설명
문제 설명
제한
양의 정수 n이 주어진다.
이 번호 k진법으로 변환할 때 다음 조건을 만족하는 소수가 변환된 수에 몇 개인지 알고 싶습니다.
- 다음과 같이 소수점 양쪽에 0이 있는 경우 예: 0P0
- P0과 같이 소수 오른쪽에 0만 있고 왼쪽에는 아무것도 없는 경우
- 다음과 같이 소수점 왼쪽에 0만 있고 오른쪽에는 아무것도 없는 경우 B.0P.
- P와 같이 소수의 양쪽에 아무 것도 없는 경우
- 단계, P는 각 자리에 0이 없는 십진수입니다.
- 101은 예를 들어 P일 수 없다
예를 들어 437674를 삼항으로 변환합니다.
211020101011입니다.
여기에 있는 소수는 211, 2, 11이며 왼쪽에서 오른쪽으로 순서대로 총 3개입니다.
(211, 2, 11 참조 211은 10진수로 볼 때 소수여야 하며 k진법으로 볼 때는 소수여야 합니다.
) P0 양식을 참조하십시오. 2는 0P0에서 11 0P에서 찾을 수 있습니다.
존재들 엔과 k는 매개변수로 지정됩니다.
N k진법으로 환산했을 때 환산된 수에 포함된 수 위 조건을 만족하는 소수의 수를 반환하려면 solve 함수를 완료하십시오.
제한
- 1 ≤ N ≤ 1,000,000
- 3 ≤ 케이 ≤ 10
I/O 예시
| N | 케이 | 결과 |
| 437674 | 삼 | 삼 |
| 110011 | 10 | 2 |
I/O 예시 설명
I/O 예제 #1
샘플 문제와 같습니다.
I/O 예제 #2
110011을 소수로 변환하면 110011이 됩니다.
여기에서 찾을 수 있는 기준을 충족하는 2개의 소수 11과 11이 있습니다.
따라서 중복된 소수를 발견하더라도 개별적으로 모두 세어야 합니다.
내 솔루션
|
데프 변경(n,k):
솔 = “”
~하는 동안 진실:
솔 = 거리(n%k) + 솔
N = N//케이
만약에 N == 0:
부서지다
돌려 주다 솔
데프 소수:
만약에 N == 0 또는 N==하나:
돌려 주다 잘못된
~을 위한 나 ~ 안에 영역(2,N//2):
만약에 n% 나 ==0:
돌려 주다 잘못된
돌려 주다 진실
데프 솔루션(들, k):
N = (거리(변경(n,k)).분할(‘0’))
N = 목록(지도(내부,(엑스 ~을 위한 엑스 ~ 안에 N 만약에 엑스 !
= ”))) 돌려 주다 (총((하나 ~을 위한 엑스 ~ 안에 N 만약에 소수(x) == 진실)))
|
CS |
잘 작동했지만 시간이 초과되었습니다.
진수 변환 함수 변경 및 소수 판별 함수 소수를 구현했는데 시간이 초과되었습니다.
결과적으로
n//2 -> (n**0,5) + 1로 프라임 검색으로 변경할 수 있습니다.
소수를 찾을 때 숫자의 제곱수에 +1까지만 틱당신이 할 수 기억
다른 솔루션
|
데프 to_k_number(n, k): # n을 기본 k로 반환
레트 = “”
~하는 동안 N > 0:
레트 += 거리(n %k)
N = N // 케이
돌려 주다 ”.join(reverse(ret))
데프 is_prime_num(k):
만약에 케이 == 2 또는 케이 == 삼: 돌려 주다 진실 #2 또는 3은 소수입니다.
만약에 케이% 2 == 0 또는 케이 < 2: 돌려 주다 잘못된 # 2의 배수이거나 2보다 작으면 소수가 아닙니다.
# 3에서 root(k)까지 2씩 증가하고 확인(3, 5, 7…),
# 작은 값의 배수에 대한 중복을 확인하고 제거합니다(소수 검색 최적화).
~을 위한 나 ~ 안에 영역(삼, 내부(케이 ** 05) + 하나, 2):
만약에 k % i == 0:
돌려 주다 잘못된
돌려 주다 진실
데프 솔루션(들, k):
답변 = 0
k_num = to_k_number(n, k) # k 진수로 반환
# n을 얻기 위해 k_num을 0으로 나눕니다.
~을 위한 N ~ 안에 k_num.split(‘0’):
만약에 N == “”: 계속해
만약에 is_prime_num(내부(N)): # n이 소수이면 답+=1
답변 += 하나
돌려 주다 답변
|
CS |