f.cpp

ACM大赛基本练习题

#include<stdio.h>

int f( int n1, int n2 )
{
	int s = n1 * n2, tmp;

	while( n1 > 0 )
	{
		tmp = n2;
		n2 = n1;
		n1 = tmp % n1;
	}

	return s / n2;
}

void make_it()
{
	int a, b, c, n;
	int ab, bc, ac, abc;
	int num;

	scanf( "%d %d %d %d", &a, &b, &c, &n );

	ab = f( a, b );
	bc = f( b, c );
	ac = f( a, c );
	abc = f( ab, c );
	
	num = n / a + n / b + n / c;
	num -= n / ab + n / bc + n / ac;
	num += n / abc;

	printf( "%d\n", num );
}

int main()
{
	int i, dataCase;

	scanf( "%d", &dataCase );

	for( i = 0; i < dataCase; ++i )
		make_it();

	return 0;
}