2013
12-23

# How many integers can you find

Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.

There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.

For each case, output the number.

12 2
2 3

7

这题有个地方很无聊，集合里面会混进0,0混进来要先删掉它才不至于在求gcd，lcm的时候RE,0本身对结果没什么影响。

12 2

2 3

12 3

1 2 3

12 4

1 2 3 0

OutPut

7

11

11

C艹代码：

#include <stdio.h>
#include <string.h>

int ans,n,m;
int arr[200],cnt;
int select[200],Lcm;

int gcd(int n,int m) {

int r = n % m;
while (r) {

n = m,m = r;
r = n % m;
}
return m;
}
int lcm(int n,int m) {

return n / gcd(n,m) * m;
}
int Solve(int n) {

int i,j,k;

for (ans = 0, i = 1; i < (1<<m); ++i) {

cnt = 0;
for (j = 0; j < m; ++j)
if (i & (1<<j)) select[++cnt] = j;

for (Lcm = j = 1; j <= cnt; ++j)
Lcm = lcm(Lcm,arr[select[j]]);

if (cnt % 2 == 1)  ans += n / Lcm;
else ans -= n / Lcm;
}
return ans;
}

int main()
{
int i,j,k;

while (scanf("%d%d",&n,&m) != EOF) {

for (i = 0; i < m; ++i) {

scanf("%d",&arr[i]);
if (arr[i] == 0) i--,m--;
}
printf("%d\n",Solve(n-1));
}
}

1. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

2. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

3. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

4. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

5. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

6. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

7. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

8. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

9. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

10. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

11. 我一向这么认为,我一直认为讨论要建立在确切的事实之上而不是我国各大新闻门户网站的评论区中的各种谣言,各种阴谋论,各种民族主义情绪. 我觉得如果批评政府的人拿不出依据,其批评完全站不住脚,那我很欢迎对其本人进行有效的反击,因为这种人缺乏最基本的思辨能力.

12. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

13. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”