如何计算Farey序列的第n阶的全部项？ UVa 10408 Farey sequences

Farey序列wiki：http://zh.wikipedia.org/wiki/%E6%B3%95%E9%87%8C%E6%95%B8%E5%88%97

关于Farey序列的相邻3项，有如下性质：

若^p?_q在某法里数列的邻项是^a?_b和^c?_d，即^a?_b < ^p?_q < ^c?_d，则有

利用该等式，设k=gcd(a+c,b+d)，

则可以计算出c=kp-a，d=kq-b。

那么k应该取多少呢？注意到两点：

1. 分母必须<=n；

2. k越大c/d越小（可用函数单调性证明），要得到下一个c/d必须使k取最大值。

由这两点可以得出k=max{k | kq-b<=n}=[(n+b)/q]

题目：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1349

完整代码：

/*0.016s*/

#include<cstdio>

void farey(int n, int ans)
{
	int k, a0 = 0, b0 = 1, a1 = 1, b1 = n, a2, b2;
	for (int i = 0; i < ans - 1; ++i) /// 由于第1项已算出(1/n)，所以算ans-1次就行
	{
		k = (n + b0) / b1;///k要尽量取大
		a2 = k * a1 - a0;
		b2 = k * b1 - b0;///利用前两项计算出下一项
		a0 = a1, a1 = a2;
		b0 = b1, b1 = b2;///移动
	}
	printf("%d/%d\n", a1, b1);
}

int main()
{
	int n, ans;
	while (~scanf("%d%d", &n, &ans))
		farey(n, ans);
	return 0;
}

如何计算Farey序列的第n阶的全部项？ UVa 10408 Farey sequences,布布扣,bubuko.com

如何计算Farey序列的第n阶的全部项？ UVa 10408 Farey sequences

原文：http://blog.csdn.net/synapse7/article/details/19967613