Given a list of integers (A1, A2, ..., An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list.
Input
The input contains several test cases.
For each test case, there are two lines. The first line contains N (1 <= N <= 10) and M (1 <= M <= 200000000), and the second line contains A1, A2, ..., An(1 <= Ai <= 10, for i = 1, 2, ..., N).
Output
For each test case in the input, output the result in a single line.
Sample Input
3 2
2 3 7
3 6
2 3 7
Sample Output
1
4
Author: MAO, Yiqiang
Source: Zhejiang University Local Contest 2007
- 设 n, k 都是正整数，S={1,2,···,n}, 则 S 中能被 k 整除的正整数的个数为 [n/k].
- 设 Ai (i=1,2,···,n) 为有限集，则
- lcm(x,y)=xy/gcd(x,y)
- lcm(x1,x2,···,xn)=lcm(lcm(x1,x2,···,xn-1),xn)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[11],n,m,ans;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
void dfs(int x,int k,int t)
{
if(x>0) ans+=m/t*k;
for(int i=x;i<n;i++)
dfs(i+1,-k,lcm(a,t));
}
int main()
{
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
cin>>a;
ans=0;
dfs(0,-1,1);
cout<<ans<<endl;
}
return 0;
}