수 [2,10]

Question

내가 어려움을 다음과 같은 문제를 해결하기 위해 노력 데

: Q 쿼리

, Q <을 = 1e6, 각 쿼리는 양의 정수 N, N < = 1e18이고, [1, N]에있는 정수의 수는 각 쿼리에 대해 [2,10]에 을 정수로 나눈 수는 없습니다.

나는 각 쿼리 (eratosthenes의 체와 유사)의 [1,1e18]에서 숫자를 필터링하기 위해 체 방법을 사용하는 것을 생각했습니다. 그러나 N의 값은 매우 클 수 있습니다. 따라서이 방법을 사용할 수있는 방법은 없습니다. 가장 유용한 관찰은 0,2,4,5,6,8로 끝나는 숫자가 유효하지 않다는 것입니다. 그러나 그것은이 문제에 도움이되지 않습니다.

적은 수의 쿼리 (Q < = 200)를 사용하는 비슷한 problem에 대한 해결책을 발견했습니다. 그러나이 문제 (그리고 그 해결책을 이해하지 못합니다)에 대해서는 작동하지 않습니다.

누군가이 문제를 해결하는 방법에 대해 조언 해 주시겠습니까?

Answer 1

유일한 문제 번호는 그 소수입니다 2, 3, 5, 7

그래서, [2,10]의 정수로 나눈 수없는 숫자는 숫자가 {2,3,5,7}

에 의해 분할 될 수없는 것입니다 가정 해 봅시다 또한 [1,n] 사이의 총 수에서 {2,3,5,7}의 조합으로 나눈 모든 수를 뺀 값과 같습니다.

이렇게 재미있는 부분은 [1,n]에서 2로 나눈 숫자는 몇 개입니까? 대답은 n/2입니다 (2 개의 숫자마다 2로 나눈 값이 있기 때문에 왜? 간단합니다)

마찬가지로 5로 나눠지는 숫자는 몇 개입니까? 대답은 n/5 ...

그럼, 아직 답을 얻었습니까? 아니요, 우리가 {2,5} 또는 {2,7} 둘로 나눈 숫자를 두 배로 늘린 것을 알았을 때, 이제는 빼내야합니다.우리는 이중 마이너스 {2,5,7-}로 나눈 것들처럼

그러나 기대는, 그래서 우리는

...

모든 때까지이 일을 계속 다시 추가 할 필요가 ... 보인다 콤비네이션은 을 처리하므로 2^4 콤비네이션이 필요합니다. 합계는 16이며 꽤 작습니다.

좋은 이해를 위해 Inclusion-Exclusion principle을 살펴보십시오.

행운을 빈다.

Answer 2

다음은이를 처리하는 방법입니다.

시작할 위치는 어떻게 조각으로 나눌 수 있는지 생각하는 것입니다. 이러한 문제로 시작해야 할 곳은 최소 공통 분모 (LCD)입니다.이 경우 2,520 개 (10 미만의 모든 숫자로 나눌 수있는 최소 숫자)입니다.

x가 2-10의 임의의 수로 나눌 수없는 경우 x + 2,520도 나눌 수 없다는 아이디어입니다. 2-10의 숫자 "서로 소"입니다 1과 2520 사이의

1. 얼마나 많은 번호 :

   따라서, 당신은 두 부분으로 문제를 분할 할 수 있습니까?

2. 목표 번호에 2,520 회가 몇 번이나 도달합니까? 나머지는 고려해야합니다. [2,10]에서