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