zoj 2836 Number Puzzle

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1836

1. 设 n, k 都是正整数，S={1,2,···,n}, 则 S 中能被 k 整除的正整数的个数为 [n/k].

2. 设 A_i (i=1,2,···,n) 为有限集，则

3. lcm(x,y)=xy/gcd(x,y).

4. lcm(x₁,x₂,···,x_n)=lcm(lcm(x₁,x₂,···,x_n-1),x_n).

5. 对于输入数据 N,M,A₁,A₂,···,A_N, 可进行数据预处理。例如：若存在 A_i=1, 答案为 M; 若存在 A_i|A_j, 可剔除 A_j, 同时 N 的值减1.

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int n,m,ans,a[10];
 5 
 6 int gcd(int a,int b){
 7     return b==0? a:gcd(b,a%b);
 8 }
 9 
10 int lcm(int a,int b){
11     return a/gcd(a,b)*b;
12 }
13 
14 void dfs(int x,int k,int t){
15     if(x>0) ans+=k*m/t;
16     for(int i=x;i<n;i++) dfs(i+1,-k,lcm(a[i],t));
17 }
18 
19 int main(){
20     while(cin>>n>>m){
21         for(int i=0;i<n;i++) cin>>a[i];
22         ans=0;
23         dfs(0,-1,1);
24         cout<<ans<<endl;
25     }
26     return 0;
27 }