제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=4790 훈련 할 때 이 문제 에 푹 빠 졌 구나. 문제 풀이 도 한참 보고 알 았 으 니 나중에 복습 할 수 있 도록 상세 하 게 문 제 를 써 보 려 고 한다.제목 은 구간 [a, b] 에서 숫자 x 를 선택 하고 구간 [c, d] 에서 숫자 y 를 선택 하여 (x + y)% p = m 를 선택 하 라 는 뜻 이다.확률 이 얼마나 되 냐 고.가장 간단 한 출력 (gcd 제외).총 이벤트 총 수 는 (b - a + 1) * (d - c + 1) 입 니 다.관건 은 만족 (x + y)% p = m 의 선택 방법 총수 입 니 다.어떻게 구 합 니까?사실 직접 구 하기는 어렵 고 시간 을 초과 하기 쉽다.우 리 는 먼저 용 척 원 리 를 이용 하여 전환 할 수 있다.f (a, b) 는 구간 0 ~ a 와 구간 0 ~ b 에서 각각 x 와 y 를 취하 여 (x + y)% p = m 의 사건 수 를 나타 낸다 고 가정 합 니 다.그러면 ans = f (b, d) - f (b, c - 1) - f (a - 1, d) + f (a - 1, c - 1).(f (a - 1, c - 1) 는 두 번 줄 었 다.그럼 f (a, b) 를 어떻게 구 하 느 냐 가 관건 입 니 다.다음은 제 가 블 로그 의 예 를 인용 하 겠 습 니 다. 예 를 들 어 f (16, 8), p = 6, m = 2. (x + y)% p = (x% p + y% p)% p 를 구하 기 때문에 0 ~ a 와 0 ~ b 두 구간 을 다시 쓰 겠 습 니 다.a 에 대해 서 는 0, 1, 2, 3, 3, 4, 0, 1, 2, 3, 4, b 에 대해 서 는 0, 2, 3, 4, 0, 1, 2, 3, 4 a 중 (0, 2, 3, 4, 5) 의 수량 이 a/p 개 이 고 b 중 (0, 1, 2, 3, 4, 5) 의 수량 은 b/p 개 이다.그래서 이에 따라 두 구간 을 네 부분 으로 나 누 었 다.이렇게 하면 A 집합 은 (0 1 2 3 4 5/0 1 2 3 4 5) 이 고 B 집합 은 (0 1 2 3 4) C 집합 은 (0 1 2 3 4 5/) 이 며 D 집합 은 (0 12) 이다.이렇게 하면 네 부분 으로 나 누 어 계산 할 수 있다.f (16, 7) = A 와 C 가 조건 을 만족 시 키 는 수 + A 와 D 가 조건 을 만족 시 키 는 수 + B 와 C 가 조건 을 만족 시 키 는 수 + B 와 D 가 조건 을 만족 시 키 는 수.1. A 와 C 가 조건 을 만족 시 키 는 수: A 중에서 하 나 를 먼저 취한 다 (0, 1, 2, 3, 4, 5). C 에서 하 나 를 취한 다 (0, 1, 2, 3, 4, 5). A 에서 하나의 수 x 를 취한 다. C 에서 임의의 한 수 y 를 더 한 p 의 나머지 범 위 는 [0 ~ 5] 이다. 즉, 하나의 x 는 하나의 y 에 대응 하고 A 중 a/p 개 (0, 1, 2, 3, 4, 5) C 중 b/p 개 (0, 1, 2, 3, 4, 5) 는 각 구간 의 p 개수 가 있 기 때문에 총 수 는 ans = (a/p) * (b/p) * 2, p.A 와 D 가 조건 을 만족 시 키 는 수: D 집합 에서 요소 의 수 mb = b% p + 1 (요소 0).(1.) 에 따라 AD 가 만족 하 는 조건 수 는 ans + = mb * (a/p) 이다.3. B 와 C 가 조건 을 만족 시 키 는 수: (2.) 와 같은 이치 로 ans + = (a% p + 1) * (b/p) 입 니 다.4. B 와 D 가 조건 을 만족 시 키 는 수: 가장 구하 기 어 려 운 것 은 바로 이것 입 니 다. 어디 에 있 는 지 구하 기 어렵 거나 앞의 차이 점 이 어디 에 있 습 니까?B 나 D 중의 임의의 원소 가 반드시 다른 집합 에 대응 하 는 것 은 아니 기 때문이다. 예 를 들 어 B 중 (3, 4, 5) 은 D 에서 대응 하지 않 는 다.그래서 우 리 는 이렇게 상황 을 나 누 었 다. (1) ma > m: (B 집합 요소: 0, 1, 2... m.. ma) ma 가 m 보다 크 면 집합 D 에서 최대 m + 1 개의 요소 (요소 0) 가 그 와 대응 하 는 것 을 의미한다. 왜 가장 많 을 까? D 집합 에서 요소 의 개 수 는 m + 1 보다 작 을 수 있 기 때문이다.그래서 ans + = min (m, mb) + 1.이게 모든 상황 인가요?사실은 그렇지 않 습 니 다. (mb + ma)% p > = m 일 때 일부 상황 이 빠 집 니 다.D 집합 에서 가장 큰 요 소 는 mb 이 고 B 에서 가장 큰 것 은 ma 이 며, 령 t = (m - ma + p)% p (mb 가 m 보다 작 으 면 t > mb?) 입 니 다.이것 은 구 한 만족 B 중 가장 큰 항목 이 D 에 대응 하 는 값 입 니 다. 만약 t < = mb 라면 D 에 mb - t + 1 개의 요소 (구간 t ~ mb) 가 대응 한 다 는 것 을 설명 합 니 다.ans+=mb-t+1. (2) 마 < = m: (B 집합 원소: 0, 1... 마) 마 < = m 시 D 집합 에서 가장 많은 마 개 원소 가 그 와 대응한다.그래서 (1) 후반 부 와 비슷 하 다.D 집합 에서 가장 큰 요 소 는 mb 이 고 B 에서 가장 큰 요 소 는 ma 이 며 똑 같이 t = (m - ma + p)% p 입 니 다.마 가 대응 하 는 D 집합 중 최대 값 이다.만약 t < = mb 라면 D 에 그 와 대응 하 는 원소 가 있다 는 것 을 설명 한다.만약 에 k 개가 있다 고 가정 하면 먼저 B 집합 에 0 이 있 고 0 이 없 으 면 B 집합 에 요소 가 없다 는 것 을 의미한다.D 에서 0 과 대응 하 는 것 은 m 이기 때문에 요소 의 개 수 는 k = m - t + 1 개 를 초과 하지 않 습 니 다.mb 는 m 보다 작 을 수도 있 습 니 다. 그 전에 토론 하지 않 았 습 니 다.그래서 k 도 mb - t + 1 개 를 넘 지 않 습 니 다.ans+=min(mb-t+1,m-t+1). 이로써 모든 상황 은 토론 이 끝났다.코드:
