【容斥定理】玲珑oj1138、hdu1796

上一篇部落客要詳講了容斥定理：點選打開連結

不過上一篇部落格隻是以3個集合為例來說明，并沒有向無限推廣；

今天這一篇部落格就是xjb搞，從其他的部落格中學來的；

1138 - 震驚，99%+的中國人都會算錯的問題

Time Limit：4s Memory Limit：128MByte

Submissions：278Solved：78

DESCRIPTION

衆所周知zhu是一個大廚，zhu一直有自己獨特的鹹魚制作技巧.

tang是一個鹹魚供應商，他告訴zhu在他那裡面有NN條鹹魚（标号從1到N）可以被用來制作.

每條鹹魚都有一個鹹魚值Ki，初始時所有Ki都是0.

zhu是一個特别的人，他有M個鹹數（鹹魚數字）, 對于每個鹹數x，他都會讓所有滿足标号是xx倍數的鹹魚的鹹魚值異或上1.

zhu現在想知道經過了這M個鹹數的篩選之後，最終有多少條的鹹魚的鹹魚值是1?

INPUT 輸入的第一行包含一個整數 T(1≤T≤1000) ，表示有 T 組資料.對于每組資料：輸入第一行隻有兩個整數 N(1≤N≤109) , M(1≤M≤15) 接下來一行有MM個整數，依次對應zhu的每個鹹數(1≤鹹數≤2∗105). OUTPUT 對于每組資料，輸出答案. SAMPLE INPUT 2 10 1 3 10 1 1 SAMPLE OUTPUT 3 10

思路：這道題目就可以了解為關燈問題；總共有n個鹹魚值，m個詢問；每次詢問使得滿足給出的鹹魚值的倍數的狀态相反；通過上一篇部落格知道三個集合的情況下為：n/a+n/b+n/c+2*(n/(a*b)+n/(a*c)+n/(b*c))+4*(n/(a*b*c));xjb搞一下，難道系數是每次增二倍？！

代碼：

#include<bits/stdc++.h>
long long ans,a[30];
int n,m;

long long gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}

void dfs(int cur,long long lcm,int id)
{
    lcm=lcm/gcd(lcm,a[cur])*a[cur];
    if(id&1)
        ans+=n/lcm*(1ll<<(id-1));
    else
        ans-=n/lcm*(1ll<<(id-1));
    for(int i=cur+1;i<m;i++)
        dfs(i,lcm,id+1);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);

        ans=0;
        for(int i=0;i<m;i++)
            scanf("%lld",&a[i]);
        for(int i=0;i<m;i++)
            dfs(i,a[i],1);

        printf("%lld\n",ans);
    }
    return 0;
}
           

      How many integers can you find

Time Limit: 12000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 8088    Accepted Submission(s): 2411

Problem Description   Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.  

Input   There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.  

Output   For each case, output the number.  

Sample Input

12 2
2 3
        

Sample Output

7
        

思路：這道題目的意思是輸入n、m，接下來輸入m個數字；這m個數字，每個數的倍數小于n的總共有有多少個？這道題也可以了解為”開燈“問題，每次輸入一個數字，打開這個數字的倍數且小于n的編号的燈泡；好啦就是這樣！

代碼：

#include<bits/stdc++.h>
long long ans,a[30];
int n,m;

long long gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}

void dfs(int cur,long long lcm,int id)
{
    lcm=lcm/gcd(lcm,a[cur])*a[cur];
    if(id&1)
        ans+=(n-1)/lcm;
    else
        ans-=(n-1)/lcm;
    for(int i=cur+1;i<m;i++)
        dfs(i,lcm,id+1);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        ans=0;
        int cnt=0;
        for(int i=0;i<m;i++)
        {
            long long x;
            scanf("%lld",&x);
            if(x>0&&x<n)      //坑點
                a[cnt++]=x;
        }

        m=cnt;
        for(int i=0;i<m;i++)
            dfs(i,a[i],1);

        printf("%lld\n",ans);
    }
    return 0;
}