GDUT1174：我是好人4（容斥定理）

1174: 我是好人4

Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 526   Solved: 103

Description

众所周知，我是好人！所以不会出太难的题，题意很简单

给你n个数，问你1000000000（含1e9）以内有多少个正整数不是这n个数任意一个的倍数

最后友情提供解题代码（我真是太好人了）

void solve(int p[], int n)

{

int ans = 0;

for (int i = 1; i <= 1e9; i++)

{

int fl = 0;

for (int j = 0; j < n; j++)

{

if (i % p[j] == 0)

{

fl = 1;

break;

}

}

if (fl == 0)ans++;

}

printf("%d\n", ans);

}

Input

第1行是一个整数T，表示共T组数据。 接下来是T组数据，每组数据第1行是正整数n（n<=50），接下来是n个正整数（小于等于1000），任意两数用1个空格隔开，最前数前面与最后数后面无空格

Output

输出T行，对应T组数据。（T<=10） 每行输出这样的正整数有多少个

Sample Input

342 3 5 71213854 101 143 282 538 922 946 286 681 977 892 656 907

Sample Output

228571428500000000968701719

HINT

提示：数据是随机生成的，尔等尽可随意乱搞

Source

# include <iostream> # include <cstdio> # include <cstring> # include <algorithm> # define LL long long using namespace std; const LL maxn = 1e9; int k, n, a[51]; LL ans = 0; LL gcd(LL x, LL y) { return y==0?x:gcd(y, x%y); } LL lcm(LL x, LL y) { return x/gcd(x, y)*y; } void dfs(int pos, int num, LL sum) { if(sum > maxn) return; if(pos == k+1) { if(num&1) ans -= maxn/sum; else ans += maxn/sum; return; } dfs(pos+1, num, sum); dfs(pos+1, num+1, lcm(sum, a[pos])); } int main() { int t; scanf("%d",&t); while(t--) { k = ans = 0; scanf("%d",&n); for(int i=1; i<=n; ++i) scanf("%d",&a[i]); sort(a+1, a+1+n); for(int i=1; i<=n; ++i)//去掉成倍数的数 { bool f = true; for(int j=k; j; --j) if(a[i]%a[j]==0) { f = false; break; } if(f) a[++k] = a[i]; } dfs(1, 0, (LL)1); printf("%lld\n",ans); } return 0; }