首页 > 代码库 > 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 ( 容斥原理 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。