題目大意：給定n和一個大小為m的集合，集合元素為非負整數。為1...n內能被集合裡任意一個數整除的數字個數。n<=2^31,m<=10
解題思路：容斥原理地簡單應用。先找出1...n內能被集合中任意一個元素整除的個數，再減去能被集合中任意兩個整除的個數，即能被它們兩只的最小公倍數整除的個數，因為這部分被計算了兩次，然後又加上三個時候的個數，然後又減去四個時候的倍數...這題很多人通過深搜來進行，我懶得寫深搜，直接枚舉狀態0...(1<<m)，然後判斷狀態內涵幾個集合元素，然後計算lcm和能被整除的個數，最後判斷下集合元素的個數為奇還是偶，奇加偶減。
這題有個地方很無聊，集合裡面會混進0,0混進來要先刪掉它才不至於在求gcd，lcm的時候RE,0本身對結果沒什麼影響。
測試數據：
12 2
2 3
12 3
1 2 3
12 4
1 2 3 0
OutPut
7
11
11
C艹代碼：
[cpp]
#include <stdio.h>
#include <string.h>
int ans,n,m;
int arr[200],cnt;
int select[200],Lcm;
int gcd(int n,int m) {
int r = n % m;
while (r) {
n = m,m = r;
r = n % m;
}
return m;
}
int lcm(int n,int m) {
return n / gcd(n,m) * m;
}
int Solve(int n) {
int i,j,k;
for (ans = 0, i = 1; i < (1<<m); ++i) {
cnt = 0;
for (j = 0; j < m; ++j)
if (i & (1<<j)) select[++cnt] = j;
for (Lcm = j = 1; j <= cnt; ++j)
Lcm = lcm(Lcm,arr[select[j]]);
if (cnt % 2 == 1) ans += n / Lcm;
else ans -= n / Lcm;
}
return ans;
}
int main()
{
int i,j,k; www.2cto.com
while (scanf("%d%d",&n,&m) != EOF) {
for (i = 0; i < m; ++i) {
scanf("%d",&arr[i]);
if (arr[i] == 0) i--,m--;
}
printf("%d\n",Solve(n-1));
}
}
