SPOJ Problem NG0FRCTN

Fractions on Tree

Explanation:

A simple problem which can be solved using recursion.
Our base case will be n = 1, for which numerator will be 1, i.e., (num = 1) and denominator also 1, (den = 1).
For n > 1, we find the value for its parent, say (num / den) by finding the value of n / 2.
Now, 
    if the child is left child, we add numerator to the denominator (den = den + num).
   else, we add denominator to the numerator (num = num + den).
Finally, return the result (num / den).

Solution:

#include<cstdio>
#include<iostream>
#include<vector>

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

vector<LLD> find_value(LLD n){

    // res[0] denotes numerator and res[1] denotes denominator.
    vector<LLD> res;
    res.resize(2);

    // Base case with n = 1. 
    if(n == 1){
        res[0] = 1;
        res[1] = 1;
        return res;
    }

    // Find the value for parent in res.
    res = find_value(n >> 1);

    // Check for left child.
    if(n == ((n >> 1) << 1))
        res[1] += res[0];
    // Check for right child.
    else
        res[0] += res[1];
    return res;
}

int main(){
 
    LLD n;
    vector<LLD> res;
    res.resize(2);
    while(true){
        scanf("%lld", &n);
        if(!n)
            break;
        res = find_value(n);
        printf("%lld/%lld\n", res[0], res[1]);
    }
    return 0;
}

Any suggestions are welcome.

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.