(p, q) 쌍의 수를 계산하는 함수 f(x)가 있다고 가정합니다.
- 1
- p와 q는 공소입니다.
- p * q =x 따라서 n이 있는 경우
범위 1에서 n까지의 모든 i에 대해 합 f(x[i])를 찾아야 합니다.
따라서 입력이 12와 같으면 x 값의 범위가 1에서 12이므로 출력은 3이 됩니다.
- x =6일 때 유효한 쌍은 (2, 3)이므로 f(6) =1
- x =10일 때 유효한 쌍은 (2, 5)이므로 f(10) =1
- x =12일 때 유효한 쌍은 (3, 4)이므로 f(12) =1
총 3쌍이 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 카운트:=0
- sqr :=(n의 제곱근) + 1의 정수 부분
- 2 ~ sqr - 1 범위의 염기에 대해
- (n / base - base + 1)의 밑과 바닥의 최소값에서 범위 1에 있는 i에 대해
- base와 i)의 gcd가 1과 같지 않으면
- 다음 반복으로 이동
- count :=count + floor of (n - i * base)/(base * base)
- base와 i)의 gcd가 1과 같지 않으면
- (n / base - base + 1)의 밑과 바닥의 최소값에서 범위 1에 있는 i에 대해
- 반환 횟수
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
수학에서 가져오기 sqrt, gcddef solve(n):count =0 sqr =int(sqrt(n)) + 1 for base in range(2, sqr):for i in range(1, min(base, n) // base - base + 1)):if gcd(base, i) !=1:계속 카운트 +=(n - i * base) // (base * base) return countn =12print(solve(n))입력
12출력
3