HDU 2588 欧拉 容斥

GCDTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 448    Accepted Submission(s): 192

Problem Description

The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

 

Input

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.

 

Output

For each test case,output the answer on a single line.

 

Sample Input

3 1 1 10 2 10000 72

 

Sample Output

1 6 260

 

//
/*把所有的n的约数找出来，然后n = p * d,那我们现在把每一个最大公约数为d的全部找出来，怎样找呢？肯定是x = q * d,显然q得与p互质，这样才能保证n跟x的最大公约数是d，然后我们就只要把所有的d找出来就行了，然后就只要找p的质因子就行了，这不就是欧拉吗？
*/
#include
#include
using namespace std;
const int Max  = 1000000005;
int num[40000],cnt2;
int Eular( int n )
{
    int ret = 1;
    for(  int i = 2; i * i <= n; ++i )
    {
        int temp = i;
        if( n % temp == 0 )
        {
            ret *= ( temp - 1 );
            n /= temp;
            while( n % temp == 0 )
                ret *= temp,n /= temp;
        }
    }
    if( n > 1 )
        ret *= ( n - 1 );
    return ret;
}
int main(  )
{
    int i,Cas;
    scanf( "%d",&Cas );
    while( Cas-- )
    {
        int n,m;
        scanf( "%d%d",&n,&m );
        cnt2 = 0;
        for(i = 1; i * i <= n; ++i )
            if( n % i == 0 )
            {
                num[cnt2++] = i;
                if( i * i < n )
                    num[cnt2++] = n / i;
            }
        int s = 0;
        for(i = 0; i < cnt2; ++i )
            if( num[i] >= m )
                s += Eular( n / num[i] );
        printf( "%d\n",s );
    }
    return 0;
}

下面是我独立的解法，采用容斥原理，重写原来的代码

/* 以10000 72为例,我们求出10000的因子为80,100,125, 这些因子恰好大于72并且互相不能整除。再使用容斥10000/80+10000/100+10000/125-10000/lcm(80,100)-10000/lcm(80,125)-10000/lcm(100,125)+10000/lcm(80,100,125)
=125+100+80-25-5-20+5=260
*/
#include
#include
#include
using namespace std;
struct fac{
    int pri; //质数
    int po;  //质数的幂
    fac(int pr, int p):pri(pr),po(p){}
};
vector fa;
vector g;
int N,M;

int gcd(int a, int b)
{
    return b==0?a:gcd(b,a%b);
}

//最小公倍数
int lcm(int a, int b)
{
   return a/gcd(a, b)*b;
}

//求N的因子，要求大于M，可能有整除冗余，例如以10000 72为例，生成250,100,200,80,125. 最终要剔除250和200
void dfs(int dep,int max,int val)
{
    int i,t=1;
    if(dep==max)
        return;
    for(i=0;i        t*=fa[dep].pri;
        if(val*t>=M){
            g.push_back(val*t);
            break;
        }
        else
            dfs(dep+1,max,val*t);
    }
    dfs(dep+1,max,val);
}


int solve()
{
    if(N==1)
        return 1;
    if(M==1)
        return N;
    int n=N;
    int i,j,cnt;

    //分解N, 生成质数因子和指数幂
    for(i=2;i*i<=n;i++){
        if(n%i==0){
            cnt=0;
            while(n%i==0){
                n/=i;
                cnt++;
            }
            fa.push_back(fac(i,cnt));
        }
    }
    if(n>1) fa.push_back(fac(n,1));
   
    //生成N的因子
    dfs(0,fa.size(),1);
    //for(i=0;i    //    printf("%d ",g[i]);
    sort(g.begin(),g.end());
   
   
    //过滤掉因子中冗余的
    int sz=g.size();
    cnt=1;
    for(i=1;i        for(j=0;j            if(g[i]%g[j]==0)
                break;
        }
        if(j==i)
            g[cnt++]=g[i];
    }

    //开始利用容斥
    int sum=0;
    for(int num=1;num<(1<        int mult=1,ones=0;
        for(i=0;i            if(num&(1<                ones++;
                mult=lcm(mult, g[i]);
            }
        }
        if(ones%2) sum+=N/mult;
        else sum-=N/mult;
    }

    fa.clear();
    g.clear();
    return sum;
}
int main(  )
{
    int Cas;
    scanf("%d",&Cas);
    while(Cas--){
        scanf("%d%d",&N,&M);
        printf( "%d\n",solve());       
    }
    return 0;
}

最早的一坨，惨不忍睹
#include
#include
int prime[30000] = {2, 3, 5, 7, 11};
int prime_count = 5;

int fac[1000000];
int count;

int temp_fac[1000000];
int temp_fac_count;

struct number_factor{
    int fac;
    int num;
}factor[20];
int factor_count;

int n, m;
int multiples[1000000];

int set[100000];
int temp_set[100000];
int critical_point;

void product(int *set, int size)
{
    int i, res = 1;

    if(!size) return;

    for(i = 0; i < size; i++)
        res *= set[i];

    if(res >= m)
        temp_fac[temp_fac_count++] = res;
}

void powerset1(int i, int *set, int size)
{
    int j;
    if(i == critical_point)
        product(set, size);
    else{
        int temp = 1;

        powerset1(i + 1, set, size);
        for(j = 1; j <= factor[i].num; j++){
            temp *= factor[i].fac;
            set[size] = temp;
            powerset1(i + 1, set, size + 1);
        }
    }
}

void de_number(void)
{
    int i, j, flag = 0;
    int number = n;   

    factor_count = 0;
    memset(factor, 0, sizeof(factor));

    for(i = 0; i < prime_count; i++){
        if(number % prime[i] == 0){
            while(number % prime[i] == 0){
                factor[factor_count].num++;
                number /= prime[i];
            }
            factor[factor_count].fac = prime[i];
            factor_count++;
        }
        if(number == 1) break;
    }
    if(number > 1){
        factor[factor_count].fac = number;
        factor[factor_count++].num++;
    }
   
    temp_fac_count = count = 0;
    critical_point = 0;

    for(i = 0; i < factor_count; i++){
        /*
        printf("%d num=%d\n", factor[i].fac, factor[i].num);
        */
        if(m <= factor[i].fac){
            fac[count++] = factor[i].fac;
            if(critical_point == 0)
                critical_point = i;
        }
        else{
            int t;
            int mult = 1;

            flag = 1;
            for(t = 1; t <= factor[i].num; t++){
                mult *= factor[i].fac;
                if(mult >= m){
                    fac[count++] = mult;
                    factor[i].num = t - 1;
                    break;
                }
            }
        }
    }
    if(critical_point == 0) 
        critical_point = factor_count;
    if(flag){
        powerset1(0, temp_set, 0);
       
        /*
        for(i = 0; i < temp_fac_count ; i++)
            printf(" temp_fac[%d]= %d\n", i, temp_fac[i]);
        */

        for(i = 0; i < temp_fac_count - 1; i++){
            for(j = 0; j < temp_fac_count -1 - i; j++)
            {
                if(temp_fac[j] > temp_fac[j + 1]){
                    int temp;
                   
                    temp = temp_fac[j];
                    temp_fac[j] = temp_fac[j + 1];
                    temp_fac[j + 1] = temp;
                }
            }
        }
        /*
        for(i = 0; i < temp_fac_count ; i++)
            printf(" temp_fac[%d]= %d\n", i, temp_fac[i]);
        */
       
        number = count;
        if(temp_fac_count) fac[count++] = temp_fac[0];
        for(i = 1; i < temp_fac_count; i++){
            for(j = number; j < count; j++)
                if(temp_fac[i] % fac[j] == 0)
                    break;
                if(j == count)
                    fac[count++] = temp_fac[i];
        }
    }
    /*
    for(i = 0; i < count; i++)
        printf("%d ", fac[i]);
    printf("\ncount= %d\n", count);
    */
}




int gcd(int a, int b)
{
    int r;

    while(a % b){
        r = a % b;
        a = b;
        b = r;
    }
    return b;
}

int lcm(int a, int b)
{
   return a/gcd(a, b)*b;
}

/*Least Common Multiple*/
int multi_lcm(int *set, int size)
{
    int i, common;
    int res = 1;

    common = fac[set[0]];
    for(i = 1; i < size; i++)
        common = lcm(common, fac[set[i]]);
    return common;
}

void set_deal(int *set, int size)
{
    int res = 1;
   
    /*
    for(i = 0; i < size; i++){
        printf("%d ", set[i]);       
    }
    printf("\n");
    */
   
    if(size){
        int temp;

        temp = multi_lcm(set, size);
        multiples[size] += n / temp;
        /*
        printf("common=%d size=%d %d\n\n", temp, size, n/temp);
        */
    }
}

void powerset(int i, int *set, int size)
{
    if(i == count)
        set_deal(set, size);
    else{
        powerset(i + 1, set, size);
        set[size++] = i;
        powerset(i + 1, set, size);
    }
}


void gcd_ext(int n, int m)
{
    int i, temp = 1;
    int total = 0;

    if(m == 1){
        printf("%d\n", n);
        return;
    }

    de_number();
    memset(multiples, 0, sizeof(int) * (count + 1));
    powerset(0, set, 0);

    for(i = 0; i < count; i++){
        total += temp * multiples[i + 1];
        temp = -temp;
    }
    printf("%d\n", total);
}

void create_prime(void)
{
    int i, j;

    for(i = 13; i < 31663; i += 6){
        int temp = i + 4;

        for(j=0; j < prime_count; j++)
            if(i % prime[j] == 0)
                break;
        if(j == prime_count)
            prime[prime_count++] = i;
   
        for(j=0; j < prime_count; j++)
            if(temp % prime[j] == 0)
                break;
        if(j == prime_count)
            prime[prime_count++] = temp;
    }
    /*
    for(i = 0; i < prime_count; i++)
        printf("%d ", prime[i]);
    printf("%d %d", prime_count, prime[prime_count - 1]);
    */
}


int main(void)
{
    int i;
    int num;

    create_prime();
   
    scanf("%d", &num);

    for(i = 1; i <= num; i++){
        scanf("%d%d", &n, &m);
        gcd_ext(n, m);
    }     

    return 0;
}