pku1377.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <math.h>

double p, q;
int cnt;
double min, target;

double Calc(int k)
{
	double val, dis;
	val = (double)(int)(k * target);
	dis = target * k - val;

	if (dis > 0.5)
	{
		dis = 1 - dis;
	}
	dis = fabs(dis);
	return dis;
}

void Solve()
{
	int i;
	double v;
	min = 1e10;
	scanf("%lf %lf", &p, &q);
	target = p / q;
	cnt = 0;
	for (i = 1; i <= q; i++)
	{
		v = Calc(i);
		if (min - v > 1e-9)
		{
			cnt++;
			min = v;
		}
	}
	printf("%d\n", cnt);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		Solve();
	}
	return 0;
}