请教大家容斥定理如何实现呢?
http://acm.zju.edu.cn/show_problem.php?pid=2836
Number Puzzle
--------------------------------------------
Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 967 Accepted Submit: 213
--------------------------------------------
Given a list of integers (A1, A2, ..., An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list.
Input
The input contains several test cases.
For each test case, there are two lines. The first line contains N (1 <= N <= 10) and M (1 <= M <= 200000000), and the second line contains A1, A2, ..., An(1 <= Ai <= 10, for i = 1, 2, ..., N).
Output
For each test case in the input, output the result in a single line.
Sample Input
3 2
2 3 7
3 6
2 3 7
Sample Output
1
4
大意是在1~M范围内求出们的倍数有几个,不要重复的.
这题是要用容斥定理的,这公式太复杂了,我只知道一种用2进制位移的方式去实现,还有别的好方法吗? 谢谢
[解决办法]
首先，更正一下。
我上次给的过程中的“然后，使A1, A2, ..., An两两互质。耗时O(n*n)。”是多余的。
下面是代码实现：
/**********************************
* Number Puzzle
*
* 容斥定理实现
*
* 编译环境: VC6.0
*
* 2007-5-12
***********************************/
#include <iostream>
using namespace std;
int TestBit( int n, int i )
{
return (n> > i)&1;
}
int gcd( int n, int m )
{
int s=n+m, temp;
n=(n> m)? n : m;
m=s-n;
while( m )
{
temp=m;
m=n%m;
n=temp;
}
return n;
}
int Count( int *list, int len, int m )
{
int i, j, Max=1 < <len;
int s=1, sum=0;
int g;
for( i=1; i <Max; ++i )
{
if(i&(i-1))
{
for( j=0; j <len; ++j )
{
if( TestBit( i, j ) )
{
g=gcd( list[j], s );
s=list[j]*s/g;
}
}
sum+=m/s;
}
}
return sum;
}
int main()
{
int n, m;
cin> > n> > m;
int *A=new int[n];
int i=0, temp;
while( i <n )
{
cin> > temp;
if( temp <=m )
A[i++]=temp;
else
--n;
}
int sum=0;
for( i=0; i <n; ++i )
sum+=m/A[i];
cout < <sum-Count(A, n, m ) < <endl;
delete []A;
return 1;
}
