Hoj 2577 Simple Computing II

基本思想都是用容斥原理。

hoj 2576 給出一組數x1...xn，問從1到m中能有多少個數能夠整除這組數中的至少一個數。

hoj 2577 給出一組數x1...xn，問從1到m中能有多少個數能夠整除這組數中的唯一的數。

其實原理都是一樣的，hoj 2576所求的情況類似於下圖：

所有被藍線覆蓋的區域大小為：x1 + x2 + x3 - x1*x2 - x1*x3 - x2*x3 + x1*x2*x3;

即奇加偶減。

hoj 2577對應的情況類似於下圖：

藍線覆蓋的區域為：x1 + x2 + x3 - 2*(x1*x2 - x1*x3 - x2*x3) + 3(x1*x2*x3);

即：仍然是奇加偶減，但是要乘以相應的等於乘數個數的系數。

hoj 2577的代碼：

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <vector>  
using namespace std; 
 
long long x[12]; 
 
long long gcd(long long a,long long b) 
{ 
    if(b == 0) 
    { 
        return a; 
    } 
    else 
    { 
        return gcd(b,a%b); 
    } 
} 
 
int main() 
{ 
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin); 
#endif  
    int t; 
    scanf(" %d",&t); 
    while(t--) 
    { 
        long long n,m; 
        long long sum = 0; 
        scanf(" %lld %lld",&n,&m); 
 
        for(long long i=0;i<n;i++) 
        { 
            scanf(" %lld",&x[i]); 
        } 
        for(long long i = 1;i<(1<<n);i++) 
        { 
            long long s = 1; 
            long long bits = 0; 
            for(long long j=0;j<n;j++) 
            { 
                if(i &(1<<j)) 
                { 
                    bits++; 
                    s *= x[j]/gcd(s,x[j]); 
                } 
            } 
            long long temp = m/s; 
            //bits是奇數時  
            if(bits&1) 
            { 
                sum +=temp*bits; 
            } 
            else 
            { 
                sum -=temp*bits; 
            } 
        } 
        printf("%lld\n",sum); 
 
    } 
} 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

long long x[12];

long long gcd(long long a,long long b)
{
    if(b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b,a%b);
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int t;
    scanf(" %d",&t);
    while(t--)
    {
        long long n,m;
        long long sum = 0;
        scanf(" %lld %lld",&n,&m);

        for(long long i=0;i<n;i++)
        {
            scanf(" %lld",&x[i]);
        }
        for(long long i = 1;i<(1<<n);i++)
        {
            long long s = 1;
            long long bits = 0;
            for(long long j=0;j<n;j++)
            {
                if(i &(1<<j))
                {
                    bits++;
                    s *= x[j]/gcd(s,x[j]);
                }
            }
            long long temp = m/s;
            //bits是奇數時
            if(bits&1)
            {
                sum +=temp*bits;
            }
            else
            {
                sum -=temp*bits;
            }
        }
        printf("%lld\n",sum);

    }
}