首页 > 代码库 > Uva 10325 The Lottery ( 容斥原理 )

Uva 10325 The Lottery ( 容斥原理 )

 

Uva 10325 The Lottery ( 容斥原理 )

 

 

#include <cstdio>#include <cstring>typedef long long LL;LL x[20],n, m;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 << m ); ++i )    {        LL mult = 1;        LL bits = 0;        for( int j = 0; j < m; ++j )        {            if( i & ( 1 << j ) )            {                mult = lcm( mult, x[j] );                if( mult > n ) break;                bits++;            }        }        if( mult > n ) continue;        if( bits & 1 )    ans += n / mult;        else            ans -= n / mult;    }    printf( "%lld\n", n - ans );}int main(){    while( ~scanf( "%lld %lld", &n, &m ) )    {        for( int i = 0; i < m; ++i )            scanf( "%lld", &x[i] );        solve();    }    return 0;}
代码君

 

Uva 10325 The Lottery ( 容斥原理 )