# Problem

Given a positive integer $N$, find the value of $g(N)$, where $$g(n) = gcd(1,n) + gcd(2,n) + gcd(3,n) + \dots + gcd(n,n) = \sum_{i=1}^n gcd(i,n)$$

For example,
\begin{align} g(6) & = gcd(1,6) + gcd(2,6) + g(3,6) + gcd(4,6) + gcd(5,6) + gcd(6,6) \\ & = 1 + 2 + 3 + 2 + 1 + 6 \\ & = 15 \end{align}

The function $g(n)$ is called GCD Sum Function for obvious reasons.

There is a paper on this topic, “The gcd-sum Function” and in this post, I will attempt to explain it as simply as possible.

# GCD Sum Function – $g(n)$

In short, there is a direct formula for calculating the value of $g(n)$.

If the prime factorization of $n$ is $p_{1}^{a_1} \times p_2^{a_2}\times \dots p_k^{a_k}$, then $$g(n) = \prod_{i=0}^k (a_i + 1)p_i^{a_i} – a_ip^{a_i-1}$$

For example, we know that $6 = 2 \times 3$. So using the formula above, we get:
\begin{align} g(6) & = \big((1+1)2 – 2^{1-1} \big) \big((1+1)3 – 3^{1-1}\big) \\ & = (4-1)(6-1) \\ & = 15 \end{align}

Very neat formula. So, as long as we can prime factorize $n$, we can easily calculate gcd-sum for $n$.

For the curious minds who want to know how we got the formula above, please proceed to next section.

## Multiplicative Function

A function $f(n)$ is called multiplicative function if:

1. $f(n)$ is defined for positive integer $n$.
2. $f(1) = 1$
3. $f(mn) = f(m)f(n)$ whenever $gcd(m,n) = 1$.

For example, the following functions are multiplicative:

## SPOJ ASCDFIB – Ascending Fibonacci Numbers

SPOJ ASCDFIB – Ascending Fibonacci Numbers is one of the earliest problems I created. This problem was used in one of the internal contests of Daffodil University. I was aiming for an easy, but a tricky problem and thus the following problem was created.

# Problem

Read the complete description of the problem from SPOJ ASCDFIB – Ascending Fibonacci Numbers.

Before you continue reading the rest of the post, please try to solve the problem on your own.

## Problem Summary

• Given $A \leq 10^5$ and $B \leq 10^6$
• Print from $fib(A)$ to $fib(A+B)$ in ascending order.
• $fib(n)$ is $n_{th}$ fibonacci number mod $10^5$.
• If there are more than $100$ terms in output, we need to print just the first $100$.
• There are $100$ test cases.