#include<iostream>
using namespace std;
typedef long long ll;
ll a[20], b[1000], sum;
inline ll gcd( ll a, ll b ){
ll t;
while ( b ){
t = a % b; a = b; b = t;
}
return a;
}
inline ll lcm( ll a, ll b ){
return b / gcd( a, b ) * a ;
}
inline ll cel ( ll a, ll b, ll num ){
return num / a - num / lcm( a, b );
}
void dfs( ll k, ll &n, ll &q, ll &num, ll id, ll now )
{
if ( k == n || id == n ){
return ;
}
ll i;
for ( i = id ; i < n ; i ++ ){
if ( k & 1 )
sum -= cel( lcm( now, a[i] ), q, num );
else
sum += cel( lcm( now, a[i] ), q, num );
dfs( k + 1, n, q, num, i + 1, lcm( now, a[i] ) );
}
}
inline ll work( ll p[], ll n, ll q, ll num){
sum = 0;
dfs( 0, n, q, num, 0, 1 );
return sum;
}
int main()
{
ll i, j, k;
ll n, m;
ll st, ed;
ll ans;
while ( scanf("%lld%lld%lld%lld",&n,&m,&st,&ed) != EOF )
{
if ( ! ( n || m || st || ed ) )
return 0;
for ( i = 0 ; i < n ; i ++ )
scanf("%lld",&a[i]);
for ( i = 0 ; i < m ; i ++ )
scanf("%lld",&b[i]);
ll q = 1;
for ( i = 0 ; i < m ; i ++ ){
if ( q <= ed )
q = lcm( b[i], q );
}
ans = work( a, n, q, st - 1 );
cout<< ( work( a, n, q, ed ) - ans ) <<endl;
}
return 0;
}
posted on 2009-09-01 01:28
Huicpc217 阅读(365)
评论(0) 编辑 收藏 引用 所属分类:
数论 、
模板