Consider
the fraction, n/d,
where n and d are
positive integers. If n
d and
HCF(n,d)=1, it is called a reduced proper fraction.
If
we list the set of reduced proper fractions for d 
8 in ascending
order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How
many elements would be contained in the set of reduced proper fractions for d 1,000,000?
题目大意：
考虑分数 n/d, 其中n 和 d 是正整数。如果 nd 并且最大公约数 HCF(n,d)=1, 它被称作一个最简真分数。
如果我们将d 8的最简真分数按照大小的升序列出来，我们得到：
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5 , 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可知该集合中共有21个元素。
d 1,000,000的最简真分数集合中包含多少个元素？
算法一（超时）：
优化技巧：
1、当分母n是素数，则以n为分母的最简真分数的数目为n-1
2、当分母和分子奇偶不同的时候，进一步检查分母和分子的最大公约数
#include<stdio.h>#include<stdbool.h>void
swap(int* a, int* b) //交换两值的函数{ int
t; t = *a; *a = *b; *b = t;} int
gcd(int
a, int
b) //求最大公约数函数{ int
r; if(a < b) swap(&a, &b); while(b) { r = a % b; a = b; b = r; } return
a;}bool
prim(int
n) //判断素数函数{ int
i; for(i = 2; i * i <= n; i++) { if(n % i == 0) return
false; } return
true;}bool
fun(int
a, int
b) //判断两整数奇偶是否相同{ return
!((a & 1) & (b & 1));}void
solve(){ int
i, j, t; long
long count = 0; for(i = 2; i <= 100000; i++) { if(i % 2 && prim(i)) { count += i - 1; continue; } count++; for(j = 2; j < i; j++) { if(fun(i,j) && (i % j != 0)) { t = gcd(i, j); if(t == 1) count++; //如果i,j互素，符合 } } } printf("%lld\n", count);}int
main(){ solve(); return
0;} |
（Problem 72）Square root convergents
原文：http://www.cnblogs.com/acutus/p/3550597.html