题意:
求1->n-1之间能被一个集合A内元素整除的数的个数,例如n = 12, A = {2, 3} 则能被A集合元素整除的数的集合为{2, 3, 4 , 6, 8, 9, 10}则结果为7。
二进制直接暴力枚举
1000MS 水过。。。re了好多次,,没想到输入忽然还有0,,,
#include<iostream> #include<cstdio> #include<string.h> using namespace std; typedef __int64 LL; LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } int main() { int i,j; LL res,lcm,num,w,n,m,a[30]={0},k; while(~scanf("%I64d %I64d",&n,&m)) { int cent=0; for(i=0; i<m; i++) { scanf("%I64d",&w); if(w!=0) //就因为这re了好久 a[cent++]=w; } n--; res=0; for(i=1; i<(1<<cent); i++) { LL bit=0; lcm=1; num=0; for(j=0;j<=cent;j++) { k=1<<j; if(k>i) { num=n/lcm; if(bit&1) res+=num; else res-=num; break; } if(k&i) { lcm=lcm*a[j]/gcd(lcm,a[j]); bit++; } } } printf("%I64d\n",res); } return 0; }
用dfs回溯算法 234MS。。。。。哎!还是要学会dfs求容斥啊
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<string> #define LL long long using namespace std; LL num[124],ans,n; int cnt; LL Gcd( LL a, LL b ) { return b == 0 ? a : Gcd( b , a%b ); } void DFS( int t , LL lcm , int c ) { lcm = num[t]*lcm/Gcd( lcm ,num[t] ); if( c&1 ) ans += n / lcm; else ans -= n / lcm; for( int i = t + 1 ; i < cnt ; i ++ ) DFS( i, lcm , c + 1 ); } int main( ) { int m; while( scanf( "%I64d %d",&n ,&m )==2 ) { bool flag = 0; cnt = 0; n--; for( int i = 0 ; i < m ; i ++ ) { scanf( "%I64d",&num[i] ); if( num[i] != 0 ) num[cnt++] = num[i]; } ans = 0; for( int i = 0 ; i < cnt ; i ++ ) { DFS( i ,num[i],1 ); } printf( "%I64d\n",ans ); } return 0; }