모 비 우 스 알고리즘 에 대한 분석

다음으로 전송:http://blog.csdn.net/herodeathes/article/details/77932208 【Problem Description】
Given 5 integers: a, b, c, d, k, you’re to find x in a…b, y in c…d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you’re only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Yoiu can assume that a = c = 1 in all test cases.
【Input】 The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases. Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
【Output】 For each test case, print the number of choices. Use the format in the example.
【Sample Input】 2 1 3 1 5 1 1 11014 1 14409 9
【Sample Output】 Case 1: 9 Case 2: 736427
【Hint】 For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).

             ，     ......      ，       。

그래, 본론 으로 돌아 가자. 최근 에 모 비 우 스 의 재연 (그래, 선생님 이 시 킨 거 야) 을 보고 재 미 있 었 다. (그래, 선생님 이 시 킨 거 야) 그래서 인정 (zao) 진 (xi) 진 (you) 의 공 부 를 시작 했다.내 영어 실력 을 보 여줄 때 가 온 것 같 아.진실 은 하나 야 -
제 시 된 n 개 질문 에 대해 매번 몇 개의 수 대 (x, y) 를 구 할 때마다 a ≤ x ≤ b, c ≤ y ≤ d 를 만족 시 키 고 gcd (x, y) = k, gcd (x, y) 함 수 는 x 와 y 의 최대 공약수 이다.100% 데이터 에 대해 a = c = 1.
이 주 제 를 다 배 운 후에 나 는 학업 에 있어 서 또 (shi) 진 (fen) 일 (tong) 보 (ku) 라 고 생각한다.나 는 이제 더 이상 말 하고 싶 지 않다. 모 비 우 스 의 재연 을 소개 해 보 자.
멍 한 텅스텐 필라멘트 리 액 션 은... 아 닙 니 다. 모 비 우 스 리 액 션 은 쉽게 말 하면 공식 입 니 다. 이 공식 으로 이미 알 고 있 는 함 수 를 통 해 이 함수 와 관련 된 또 다른 함수 의 값 을 유도 할 수 있 습 니 다.좀 꼬 인 것 같은 데??괜찮아, 프로그래머 는 이런 세부 사항 에 신경 쓸 필요 가 없어.여기 서 는 간략하게 말 할 뿐이다.그것 이 가 져 온 수론 연산 을 간소화 하 는 효 과 는 다른 알고리즘 과 비교 하기 어렵다.
공식 은 다음 과 같다. G (n) = sigma (F (d)) (그 중에서 d | n) (집합 포함) 는 사실 재연 에 또 다른 집합 공식 이 있다. 그러나 그것 은... 폐 기 된 것 이 고 ACM 이 나타 나 지 않 았 기 때문에 이것 을 먼저 배 웠 다.이 공식 을 통 해 우 리 는 F 와 G 의 관 계 를 알 수 있다. G (1) = F (1) G (2) = F (1) + F (2) G (3) = F (1) + F (3) G (6) = F (1) + F (2) + F (3) + F (6) 다음은 용 척 원리 이다. G 로 F 의 값 을 표현 할 때 그 를 사용 하기 때문이다.그래서 각 식 앞의 G 는 하나의 계수 (- G 와 G, 아 참, 그리고 0 * G, 즉 나타 나 지 않 음) 가 있 습 니 다. 그리고 우 리 는 오로라 함 수 를 통 해 F (n) 를 구 할 때 G (d) 의 계 수 를 얻 습 니 다.그러면 남 은 문 제 는 G 의 계수!!!우 리 는 구 해 F (6) 를 예 로 들 어 설명 하고 하나의 계수 함수 H (d, n) 를 정의 한다. 그 중 H (d, n) 가 구 해 F (n) 를 표시 할 때 G (d) 의 계수 (그 중 d | n) 를 얻 을 수 있 기 때문에 이 식 의 F (6) = H (6, 6) * G (6) + H (2, 6) * G (2) + H (3, 6) G (3) + H (3) G (3) + H (1, 6) G (1) 를 얻 을 수 있다. 우 리 는 a, b, c, d 로 각각 4 개의 H (6, 6), H (2, 6), H (2, 6), H (3, 6), H (3, 6), H (3, 6) G (3) + H (3) + 의 G 를 F 로 표시 하고,F (6) = a * (F (6) + F (3) + F (2) + F (2) + F (1) + b * (F (2) + F (1) + c * (F (3) + c * (F (3) + F (1) + d * F (1) 다시 변형 시 켜 F (6) * (a - 1) + F (3) * (a + c) + F (2) + F (2) * (a + c) + F (2) * (a + b) + F (1) + F (1) * (a + b + b + c + c + c + c (1) * (1) * (a + b + c + c + c + c + c + c + c + c + c + c + d) = 0 = 0, F (6) = 0, F (6) 방정식 팀!!a-1==0 a+c==0 a+b==0 a+b+c+d==0
이렇게 하면 항상 해 를 찾 을 수 있 으 니, 나 에 게 왜 냐 고 묻 지 마라, 그 무슨 방정식 인지 알 겠 니?
그러면 결론 을 하나 더 내 면 계산 과정 이 복잡 하지 않다 는 것 을 스스로 증명 할 수 있다.H (a, b) 는 모두 H (1, b / a) 라 고 쓸 수 있 습 니 다. 그래서 우 리 는 H 의 첫 번 째 요 소 를 생략 하고 H (x) 라 고 간략하게 말 하면 H 와 U 를 연결 시 킬 수 있 습 니 다. 사실은 U (x) = H (x) = H (1, x) 를 다시 하면 우 리 는 U (x) 에 더욱 구체 적 인 의 미 를 부여 할 수 있 습 니 다. U (x) 는 F (x) 를 계산 할 때 G (1) 의 계 수 를 표시 합 니 다!(U (x) = = H (1, x) 때문에)
다음은 위 에 있 는 U (x) 의 새로운 의미 로 U (x) 의 값 을 계산 하 는 방법 을 시도 해 보 겠 습 니 다!!일단 확실하게 2 점!하 나 는 G (x) 에 F (1) 가 포함 되 어 있 습 니 다. 1 | x 2 는 F (1) = G (1) 이기 때 문 입 니 다.
(0). 만약 x = = 1 이 F (1) = G (1) 때문에 U [1] = 1;
(1). 만약 에 x 가 하나의 질 수 F (x) = U (1) G (x) + U (x) G (1) 를 U (1) = 1 로 가 져 간다 고 가정 하면 G (x) 에 F (1) 가 하나 있 고 왼쪽 에 F (1) 가 없 기 때문에 우 리 는 G (1) 를 이용 하여 F (1) 를 없 애 야 하기 때문에 U (x) = - 1 을 얻 을 수 있다.
(2). x 가 2 개의 서로 다른 질수 의 곱 하기 x = p * q 로 쓸 수 있다 고 가정 하면 F (x) = U (1) * G (pq) + U (q) * G (p) + U (p) * G (q) + U (x) * G (1) 여기 U (1), U (p), U (q) 는 앞의 2 가지 상황 대 입 계수 이다. 왼쪽 에 F (1) 가 없 기 때문에 오른쪽 F (1) 를 상쇄 하기 위해 우 리 는 U (x) = 1 이 필요 하 다.
(3). 만약 x 가 3 개의 서로 다른 질의 곱 하기 x = p * p1 * p2 로 쓸 수 있다 고 가정 하면 우 리 는 z = p1 * p2 F (x) = U (1) * G (pz) + U (z) * G (p) + U (p) G (z) + U (x) G (1);그 중에서 U (1), U (p), U (z) 는 각각 앞의 몇 가지 상황 으로 가 져 온 후에 F (1) 를 상쇄 하기 위해 U (x) = - 1 을 얻 으 면 똑 같은 방식 으로 아래로 전달 할 수 있 고 첫 번 째 결론 을 얻 을 수 있 습 니 다. 만약 에 x = p1 * p2... * pr, 그 중에서 pi 가 서로 다른 질 수 라면 U [x] = (- 1) ^ r - - - - - 1!!
(4). 만약 x 가 하나의 질 수의 제곱 x = p ^ 2 F (x) = U (1) * G (x) + U (p) * G (p) + U (x) * G (1) 대 입 계 수 를 U (x) = 0 으로 쓸 수 있다 고 가정 합 니 다.
(5). 만약 x 가 하나의 질수 로 쓸 수 있 는 3 차원 x = p ^ 3 F (x) = U (1) * G (x) + U (p) * G (p ^ 2) + U (p ^ 2) * G (p) + U (x) * G (1) 가 계수 에 들 어간 후 U (x) = 0;이 를 통 해 같은 방식 으로 아래로 전달 하여 두 번 째 결론 을 얻 을 수 있 습 니 다. 만약 x = p ^ e (e > 1) U [x] = 0; - - –2！！
(6). x 를 x = p ^ e * q 로 쓸 수 있다 고 가정 하면 p, q 는 서로 다른 질 수 입 니 다. e > 1 F (x) = U (1) * G (x) + U (q) * G (p ^ e) + U (p ^ e) * G (q) + U (x) * G (1) 대 입 계수 후 U (x) = 0;
이 를 통 해 계속 아래로 밀 어 붙 여 제2 조 결론 을 얻 을 수 있 는 강화 판!!만약 x = p ^ e * z 중 p 가 질 수 이 고 z 가 임 의 수 라면 e > 1 그러면 U [x] = 0
거의 다 르 지 않다.
끝 난 줄 알았어?코드 소개 할 까요?헤헤, 자, 너 를 계속 괴 롭 히 는 이 문 제 를 어떻게 풀 것 인 가 를 먼저 말 해 봐.이 문 제 는 비교적 징 그 러 운 점 이 있 는데 데 이 터 는 k = = 0 이 있 는데 이때 분명히 답 은 0 이 고 두 개의 숫자 가 없 는 gcd 는 0 이다.우선 gcd 는 소 용이 없습니다.gcd 를 약속 한 후 두 개의 수치 가 서로 질 적 이기 때문이다.그래서 우 리 는 x / = k y / = k 를 가설 하고 x < = y 를 가설 한 다음 에 문 제 는 구간 [1. x] 과 [1. y] 중의 상호 질량 수가 몇 쌍 인지 2 개의 수로 바 뀌 었 다.이 문 제 는 1 - 3 과 3 - 1 의 경우 한 가지 로 계산 해 야 하기 때문에 x 만 제한 하면 된다.

#include
#include
#include
#include using namespace std; const int maxn=1000000; bool check[maxn+10]; //           int prime[maxn+10]; //        int U[maxn+10];//      void get_Mobius() {
    memset(check,0,sizeof(check));
    U[1]=1;
    int tot=0;
    for(int i=2;i<=maxn;i++)
    {
        if(check[i]==0)
        {
            prime[tot++]=i;
            U[i]=-1;//      ，1      
        }
        for(int j=0;jif(i*prime[j]>maxn)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                U[i*prime[j]]=0;//          
                break;
            }
            else
            {
                U[i*prime[j]]=-U[i];//        ，       
            }
        }
    } } /*    F（t）=  gcd(x,y)%t==0       f(t)=  gcd(x,y)=t     ， F（t） f(t)             。  F（t）=(b/t)*(d/t)      gcd(x,y)=1, gcd(x?k,y?k)=k，     b d    k，    f(1)       。 lim=min(b/k,d/k),                  ， 
*/ int main() {;
    int T;
    int a,b,c,d,k;
    get_Mobius();
    scanf("%d",&T);
    for(int ii=1;ii<=T;ii++)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0)
        {
            printf("0
");
            continue;
        }
        b/=k;a/=k;
        d/=k;c/=k;
        if(b>d)swap(b,d);
        long long ans1=0;
        for(int i=1;i<=b;i++)
            ans1+=(long long)U[i]*(b/i)*(d/i);//   G(n)        F(1) = sigma(U[i]*(a/i)*(b/i)) (1<=i<=N)
        long long ans2=0;
        for(int i=1;i<=b;i++)
            ans2+=(long long)U[i]*(b/i)*(b/i);//             
        ans1-=ans2/2;
        printf("%lld
",ans1);
    }
    return 0; }