首页 > 代码库 > ZOJ 2836 Number Puzzle ( 容斥原理 )

ZOJ 2836 Number Puzzle ( 容斥原理 )

 

ZOJ 2836 Number Puzzle ( 容斥原理 )

 

 

 

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;#define CLR( a, b ) memset( a, b, sizeof(a) )int m, n, A[11];LL gcd( LL a, LL b ){    return b == 0 ? a : gcd( b, a % b );}LL lcm( LL a, LL b ){    return a / gcd( a, b ) * b;}void solve(){    LL ans = 0;    for( int i = 1; i < ( 1 << n ); ++i )    {        LL mult = 1;        LL bits = 0;        for( int j = 0; j < n; ++j )        {            if( ( 1 << j ) & i )            {                mult = lcm( mult, A[j] );                bits++;            }        }        if( bits & 1 )            ans += m / mult;        else            ans -= m / mult;    }    printf( "%lld\n", ans );}void Orz(){    while( ~scanf( "%d %d", &n, &m ) )    {        for( int i = 0; i < n; ++i )            scanf( "%d", &A[i] );        solve();    }}int main(){    Orz();    return 0;}
代码君

 

ZOJ 2836 Number Puzzle ( 容斥原理 )