SPOJ Problem MATHS

Mathematics

Explanation:

The problem demands to find two values.

1. No. of terms in Farey sequence with denominator less than or equal to n.
2. m_th fraction in Farey sequence of n.

For the first value, we use the formula:
Terms in Farey(n) = 1 + φ(1) + φ(2) ... + φ(n-1) + φ(n).
To solve this, we first find out φ values for each n from 1 to 1000000.
We get φ(1) = 1, but to ease further computations, I added 1 to it and then applied dynamic programming to find the corresponding results as described in function "init_and_calculate_phi".

To find the second value, I converted the next term implementation as shown here into C++ which can be found in function "find_term".

Solution:

#include<cstdio>
#include<iostream>

#define size 1000001
typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

LLD phi[size];

void init_and_calculate_phi(){

    // Find the φ value for each n.

    for(int i=1;i<size;i++)
        phi[i] = i-1;
    for(int i=2;i<size/2;i++){
        if(phi[i] == i-1)
            for(int j=i*2;j<size;j+=i)
                phi[j] -= phi[j] / i;
    }

    // Find the no. of terms by adding the sum of previous φ values to current φ value.

    phi[1] = 2;
    for(int i=2;i<size;i++)
    phi[i] += phi[i-1];

    // At the end, phi[n] will store no. of terms
    // in Farey sequence of denominator less than or equal to n.
}

void find_term(int n, int m){

    // If first term is to be found.
    if(m == 1){
        printf("0/1 ");
        return;
    }
    // If second term is to be found.
    if(m == 2){
        printf("1/%d ", n);
        return;
    }
    // If last term is to be found.
    if(phi[n] < 100000 && m == phi[n]){
        printf("1/1 ");
        return;
    }

    // Calculate the value using the next term implementation.
    int a = 0, b = 1, c = 1, d = n, k, tc, td;
    bool flag = false;
    if(m > (phi[n] + 1) >> 1){
        m = phi[n] + 1 - m;
        flag = true;
    }
    for(int i=3;i<=m;i++){
        k = int((n + b)/d);
        tc = c;
        td = d;
        c = k * c - a;
        d = k * d - b;
        a = tc;
        b = td;
    }
    if(flag)
        printf("%d/%d ", d - c, d);
    else
        printf("%d/%d ", c, d);
}

int main(){
 
    int n, m;

    // calculate the no. of terms for 
    // Farey sequence from 1 to (size - 1)
    // and stores in array "phi".

    init_and_calculate_phi();

    while(true){
        scanf("%d%d", &n, &m);
        if(!n && !m)
            break;

        // Find the mth fraction in Farey sequence of n.

        find_term(n, m);
        printf("%lld\n", phi[n]);
    }
 
    return 0;
}

Any suggestions are welcome.