Wu Yudong's Blog

Counting fractions

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:

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

分数计数

考虑形如n/d的分数，其中n和d均为正整数。如果n < d且其最大公约数为1，则该分数称为最简真分数。

如果我们将d ≤ 8的最简真分数构成的集合按大小升序列出，我们得到：

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;
}

算法二：

将1~1000000的整数分奇偶两部分计算，依然超时

#include<stdio.h>
#include<stdbool.h>

#define N 1000000
 
int gcd(int a, int b)  //求最大公约数函数
{
    int r;
    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 <= N; i += 2) {
        count++;
        for(j = 3; j < i; j += 2) { 
            t = gcd(i, j);
            if(t == 1) count++;
        }
        
    }
    for(i = 3; i < N; i += 2) {
        count++;
        if(prim(i)) {
            count += i - 1;
            continue;
        } else {
            for(j = 2; j < i; j++) {
                if(gcd(i, j)) count++;
            }
        }
        
    }
    printf("%lld\n", count);
}
 
int main()
{
    solve();
    return 0;
}

算法三：

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

#define N 1000001

bool a[N];

void Eratosthenes()
{
    int i, M, j;
    for(i = 2; i < N; i++) {
        a[i] = true;
    }
    M = (int)sqrt(N);
    for(i = 2; i <= M; i++) { 
        if(a[i]) {
            j = i * i;
            for(; j < N; j += i)
                a[j] = false;
        }
    }
}

int fun(int n)
{
    int t, i, count, j;
    t = n / 2;
    i = 2;
    count = n - 1;
    while(i <= t) {
        if(a[i]) {
            if(n % i == 0) {
                count--;
                for(j = i; j * i < n; j++) {
                    count--;
                }
            }
        }
        i++;
    }
    return count;
}
  
int main()
{
    int i;
    long long count = 0;
    
    Eratosthenes();

    for(i = 2; i < N; i++) {
        if(a[i]) {
            count += i - 1;
        } else {
            count += fun(i);
        }
    }
    printf("%lld\n", count);
    
    return 0;
}

 算法四：使用欧拉函数

//（Problem 72）Counting fractions
// Completed on Tue, 18 Feb 2014, 14:08
// Language: C11
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com

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

#define N 1000001

int phi[N];     //数组中储存每个数的欧拉数

void genPhi(int n)//求出比n小的每一个数的欧拉数(n-1的)
{
    int i, j, pNum = 0 ;
    memset(phi, 0, sizeof(phi)) ;
    phi[1] = 1 ;
    for(i = 2; i < n; i++)
    {
        if(!phi[i])
        {
            for(j = i; j < n; j += i)
            {
                if(!phi[j])
                    phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

void solve()
{
    int i;
    long long ans =0;
    for(i = 2; i < N; i++) {
        ans += phi[i];
    }
    printf("%lld\n", ans);
}

int main()
{
    genPhi(N);
    solve();
    return 0;
}

Answer:303963552391

Completed on Tue, 18 Feb 2014, 22:08