题目链接：https://projecteuler.net/problem=73
n/d的真分数 ，当d《=12000时 在 1/3 and 1/2 之间的有多少个
public class P73{
void run(){
FareySequences();
}
void FareySequences(){
int limit = 12000;
int a = 1;
int b = 3;
int c = 4000;
int d = 11999;
int count=0;
while(!(c==1 && d==2)){
count ++;
int k = (limit+b)/d;
int e = k*c -a;
int f = k*d -b;
a = c;
b = d;
c = e;
d = f;
}
System.out.println(count);
}
// 7295372
// 117ms
void BruteForce2(){
int max_n = 12000+1;
int result=0;
for(int i=5;i<max_n;i++){
for(int j=i/3+1;j<(i-1)/2+1;j++){
if(gcd(i,j)==1){
result++;
}
}
}
System.out.println(result);
}
// 7295372
// 1923ms
void BruteForce(){
int max_n = 12000+1;
double target2=0.5;
double target1=1/3.0;
int result=0;
for(int i=5;i<max_n;i++){
for(int j=i+1;j<max_n;j++){
if(gcd(i,j)==1){
double tmp = i/(j*1.0);
if(tmp>target1 && tmp<target2)
result++;
}
}
}
System.out.println(result);
}
// 7295372
// 8877ms
int gcd(int a,int b){
int temp;
if(a<b){
temp =a;
a = b ;
b = temp;
}
while(b!=0){
temp = a%b;
a = b;
b = temp;
}
return a;
}
void calculate(){
int max_n = 1000000;
long a = 3;
long b = 7;
long r = 0;
long s = 1;
int q = 0;
long p = 0;
for( q = max_n;q>2;q--){
p = (a*q-1)/b;
if(p*s>r*q){
s = q;
r = p;
}
}
System.out.println(r+"/"+s);
}
boolean isPrime(int num){
if(num==2||num==3) return true;
if(num<2) return false;
for(int i=5;i<Math.sqrt(num)+1;i++)
if(num%i==0) return false;
return true;
}
long[] cal_phi(int max_n){
long[] phi = new long[max_n+1];
for(int i=1;i<max_n;i++){
phi[i] += i;
for(int j =2*i;j<max_n;j+=i)
phi[j]-=phi[i];
}
return phi;
}
public static void main(String[] args){
long t0 = System.currentTimeMillis();
new P73().run();
long t1= System.currentTimeMillis();
System.out.println((t1-t0)+"ms");
}
}