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;elseans += 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; }

轉載于:https://www.cnblogs.com/junior19/p/6729930.html

總結

以上是生活随笔為你收集整理的GDUT1174：我是好人4（容斥定理）的全部內容，希望文章能夠幫你解決所遇到的問題。

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