兩題的鏈接先給上：

http://acm.hit.edu.cn/hoj/problem/view?id=2576

http://acm.hit.edu.cn/hoj/problem/view?id=2577

?

下面兩題都是很經典的容斥原理的題目，自己做的時候有點瞎yy，所以下面的表達不太嚴謹。。。

HOJ 2576 Simple Computing

My Tags

容斥原理???(Edit)

?	Source?:?ACMGroup
?	Time limit?: 1 sec	?	Memory limit?: 32 M

Submitted?: 391,?Accepted?: 123

Given n integers x₁?x₂?... x_n, you should count how many intergers from 1 to m that can be divided by at least one of them.

?Input

?The first line is an integer c which shows the number of cases. Each case contains 2 lines. The first line has 2 integers n and m. The second line contains n integers. (0<n<11, 0<m<2^31, 0<x_i<100)

?Output?

For each case print the answer in a single line.

?Sample Input

2 1 10 2 2 20 3 4

Sample Output

5 10

題目大意：
　　給出一組數a1...an，問從1到m中能有多少個數能夠最少能被這組數中的一個整除

分析：
容斥原理可以解決1-n中與m互質的數的個數問題，做法是把m分解成幾個素因子，然后利用容斥原理求解。由于p1..pk都是素數，所以
gcd(pi,pj) == 1。
而這題變成了n個數（包含合數）。所以在求解過程中乘完之后還得除以最大公約數。不然如3,6，m =18時，答案是6。在計算的時候，6，12很明顯能夠同時被3,6整除。

代碼如下：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;#define debug puts("here")typedef long long ll;const int X = 105;int size; int di[X];int gcd(int x,int y){return x==0?y:gcd(y%x,x); }void cal(ll n){ll sum = 0;for(int i=1;i<(1<<size);i++){ll s = 1;bool ok = false;for(int j=0;j<size;j++)if( i & (1<<j) ){s = s/gcd(s,di[j])*di[j];ok = !ok;}if(ok)sum += n/s;elsesum -= n/s;}cout<<sum<<endl; }int main(){ #ifndef ONLINE_JUDGEfreopen("suma.txt","r",stdin); #endifint ncase,m;cin>>ncase;while(ncase--){scanf("%d%d",&size,&m);for(int i=0;i<size;i++)scanf("%d",&di[i]);cal(m);}return 0; }

　　

另外變形的一題

Simple Computing II

My Tags

容斥原理???(Edit)

?	Source?:?ACMGroup
?	Time limit?: 1 sec	?	Memory limit?: 32 M

Submitted?: 173,?Accepted?: 63

Given n integers x₁?x₂?... x_n, you should count how many intergers from 1 to m that can be divided exactly by only one of them.

Input

The first line is an integer c which shows the number of cases. Each case contains 2 lines. The first line has 2 integers n and m. The second line contains n integers. (0<n<11, 0<m<2^31, 0<x_i<100)

Output

For each case print the answer in a single line.

Sample Input

2 1 10 2 2 20 3 4

Sample Output

5 9

題目:
　　給出n個數，現在問從1到m只能夠被這n個數中的一個數整除的個數

分析：
　　我們上一題是最少能夠被這n個數中的一個整除，所以我們可以很容易用容斥解決掉。
　　那么這題其實就相當于那題的稍微變形，求的是只能夠被n個數中的一個整除。直觀上
　　來看，我們需要把兩個或者兩個以上的去掉。所以還是用容斥來做，只不過在加減的
　　時候需要控制一下就好了。
　　1.在只有兩個的時候，減掉的個數*2。
　　2.在加三的時候，由于在減二時多減了，所以我們得要加回來，然后再減掉自己那個部分，剛好是*3。
　　3.同樣，在擁有i個數的時候：
　　　　i 奇數 + s*i
　　　　i 偶數 - s*i

代碼
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;#define debug puts("here")typedef long long ll;const int X = 105;int size; int di[X];int gcd(int x,int y){return x==0?y:gcd(y%x,x); }void cal(ll n){ll sum = 0;for(int i=1;i<(1<<size);i++){ll s = 1;int ok = 0;for(int j=0;j<size;j++)if( i & (1<<j) ){s = s/gcd(s,di[j])*di[j];ok ++;}if(ok&1)sum += n/s*ok;elsesum -= n/s*ok;}cout<<sum<<endl; }int main(){ #ifndef ONLINE_JUDGEfreopen("suma.txt","r",stdin); #endifint ncase,m;cin>>ncase;while(ncase--){scanf("%d%d",&size,&m);for(int i=0;i<size;i++)scanf("%d",&di[i]);cal(m);}return 0; }

　　

轉載于:https://www.cnblogs.com/yejinru/archive/2013/01/17/2865217.html

總結

以上是生活随笔為你收集整理的HOJ 2576 HOJ 2577 Simple Computing I II 容斥原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。