求1~n中与m互质的数的个数（m>n）附hdu1695题解(欧拉函数+容斥原理)

53 阅读 0 评论 35 点赞

我是靠谱客的博主糊涂秀发，最近开发中收集的这篇文章主要介绍求1~n中与m互质的数的个数（m>n）附hdu1695题解(欧拉函数+容斥原理)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

int calc(int n,int m) { //求1~n 与m互质的数的个数
    int num=getFactors(m);  //先将m分解质因数
    int sum=0;  //先求出不互质的个数，最后用n减去该数
    for(int state=1; state<(1<<num); state++) {   //枚举状态
        int tmp=1;
        int cnt=0;  
        for(int i=0; i<num; i++) {
            if(state&(1<<i)) {
                cnt++;
                tmp*=p[i];
            }
        }
        if(cnt&1)sum+=n/tmp;   //容斥
        else sum-=n/tmp;
    }
    return n-sum;
}

//以下是题解

http://acm.hdu.edu.cn/showproblem.php?pid=1695

GCD

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4272 Accepted Submission(s): 1492
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).

声明：此处搬运的kuangbin的题解，本人太懒。。

题意: 在1~a, 1~b中挑出(x,y)满足gcd(x,y) = k , 求(x,y) 的对数 , a,b<=10^5

思路: gcd(x, y) == k 说明x,y都能被k整除, 但是能被k整除的未必gcd=k , 必须还要满足

互质关系. 问题就转化为了求1~a/k 和 1~b/k间互质对数的问题

可以把a设置为小的那个数, 那么以y>x来保持唯一性(题目要求, 比如[1,3] = [3,1] )

接下来份两种情况:

1. y <= a , 那么对数就是 1~a的欧拉函数的累计和(容易想到)

2. y >= a , 这个时候欧拉函数不能用了,怎么做?　　可以用容斥原理，具体见代码：

最后附上自己写的代码：

#include<queue>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
using namespace std;
typedef long long LL;
const int maxn=100000;
bool check[maxn+7];
int phi[maxn+7];
int prime[maxn+7];
int tot; //素数的个数
void phi_and_prime_table(int N) {
    memset(check,false,sizeof(check));
    phi[1]=1;
    tot=0;
    for(int i=2; i<=N; i++) {
        if(!check[i]) {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0; j<tot; j++) {
            if(i*prime[j]>N)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            } else {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
int p[107],dex[107];
//设最大的素数为t，则x最多能取t*t
int getFactors(LL x) {  //将x的唯一分解存在p[]和dex[]中
    int fatcnt=0;
    LL tmp=x;
    for(int i=0; prime[i]<=tmp/prime[i]; i++) {
        dex[fatcnt]=0;
        if(tmp%prime[i]==0) {
            p[fatcnt]=prime[i];
            while(tmp%prime[i]==0) {
                dex[fatcnt]++;
                tmp/=prime[i];
            }
            fatcnt++;
        }
    }
    if(tmp!=1) {
        p[fatcnt]=tmp;
        dex[fatcnt++]=1;
    }
    return fatcnt;
}
int calc(int n,int m) { //求1~n 与m互质的数的个数
    int num=getFactors(m);  //先将m分解质因数
    int sum=0;  //先求出不互质的个数，最后用n减去该数
    for(int state=1; state<(1<<num); state++) {   //枚举状态
        int tmp=1;
        int cnt=0;
        for(int i=0; i<num; i++) {
            if(state&(1<<i)) {
                cnt++;
                tmp*=p[i];
            }
        }
        if(cnt&1)sum+=n/tmp;   //容斥
        else sum-=n/tmp;
    }
    return n-sum;
}
int q,a,w,b,k,aa,bb;
int main() {
    // freopen("in.txt","r",stdin);
    phi_and_prime_table(maxn);
    int t;
    cin>>t;
    int now=0;
    while(t--) {
        scanf("%d%d%d%d%d",&q,&aa,&w,&bb,&k);
        if(k == 0 || k > aa || k > bb) {
            printf("Case %d: 0n",++now);
            continue;
        }
        if(bb>aa)swap(aa,bb);
        a=aa/k,b=bb/k;
        LL ans=0;
        for(int i=1; i<=b; i++) {
            ans+=phi[i];
        }
        for(int i=b+1; i<=a; i++) {
            ans+=calc(b,i);
        }
        printf("Case %d: %I64dn",++now,ans);
    }
    return 0;
}