Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1522
容斥原理。很轻松就AC掉。
但是另一道题——此题M为10^4，另一道题M为10^9——却总也A不掉。
以下是1522的代码：
#include <iostream>using namespace std;int main(){ bool *num = (bool*)malloc(sizeof(bool)*10000+1); int n,m,i,j,x; while(scanf("%d %d", &n, &m)!=EOF) { memset(num, false, sizeof(bool)*m+1); for (i=0; i<n; i++) { scanf("%d", &x); for (j=x; j<=m; j=j+x) { num[j] = true; } } for (x=0,i=1; i<=m; i++) { if (!num[i]) x++; } printf("%d/n", x); } free(num); return 0;}
后来想了一下，可以求出n个数的最小公倍数，然后计算公倍数以内的数再去做适当的运算即可。试了有一阵子，在1522过了，但是另一道还是不行。老是MLE。哎
以下是计算出最小公倍数的代码：
#include <iostream>using namespace std;double gcd(double a, double b){ int t,z; double x=a, y=b; if (a<b) { t = a; a = b; b = t; } while(b!=0) { z = a/b; t = a-z*b; a = b; b = t; } return x/a*y;}int main(){ bool *num; double min,mintemp; int n,m,i,j,x[15],out,mul,ct; while(scanf("%d %d", &n, &m)!=EOF) { min = 1; for (i=0; i<n; i++) { scanf("%d", &x[i]); min = gcd(min, (double)x[i]); } if (min>(double)m) min=m; mintemp = (int)min; num = (bool*)malloc(sizeof(bool)*mintemp+1); memset(num, false, sizeof(bool)*mintemp+1); for (i=0; i<n; i++) { for (j=x[i]; j<=mintemp; j=j+x[i]) { num[j] = true; } } mul = m/mintemp; out = m-mul*mintemp; ct = 0; for (i=1; i<=mintemp; i++) { if (!num[i]) ct++; } ct *= mul; for (i=1; i<=out; i++) { if (!num[i]) ct++; } printf("%d/n", ct); free(num); } return 0;}
明天再想了= =
++++++++++++++++++++++++++++++++++++++++++++++时间分隔线
今天早上起床，坐在床上想了一会，想出了一个方法。
发现这才是真正的容斥原理啊！！
思路就是把每一个数的最小公倍数的m以内的倍数的个数加起来。
然后把每两个数的最小公倍数的m以内的倍数的个数减掉。
然后把每三个数的最小公倍数的m以内的倍数的个数加起来。
……
到最后就是所求答案了。
DEBUG之后提交，一次AC，哈哈！
#include <iostream> #include <vector> using namespace std; vector<double>v[15]; double m,x[15]; int n; double gcd(double a, double b) { int t,z; double x=a, y=b; if (a<b) { t = a; a = b; b = t; } while(b!=0) { z = a/b; t = a-z*b; a = b; b = t; } return x/a*y; } void cal(int i, int num, double min) { if (i<n) { cal(i+1, num+1, gcd(min, x[i])); cal(i+1, num, min); } else if (i==n) { v[num].push_back(min); } } int main() { int i,j,ct; while(scanf("%d %lf", &n, &m)!=EOF) { for (i=0; i<n; i++) { scanf("%lf", &x[i]); } for (i=0; i<n; i++) { v[i].clear(); } cal(0,0,1); ct = 0; for (i=1; i<=n; i++) { if (i%2==1) { for (j=0; j<v[i].size(); j++) { if (v[i][j]<m) { ct += (int)(m/v[i][j]); } } } else { for (j=0; j<v[i].size(); j++) { if (v[i][j]<m) { ct -= int(m/v[i][j]); } } } } printf("%d/n", (int)m-ct); } return 0; }
p.s.发现原来代码是这样插入的啊，哈哈哈哈哈！！！
