# Sum of the number divided by its GCD

Problem:

Given a formula:

GCD (x, y) means the GCD (greatest common divisor) of x and y.

For example: if N = 2, then:

• f (2) = 1 / GCD (1, 4) + 2 / GCD (2, 4) + 3 / GCD (3, 4) + 4 / GCD (4.4)
• f (2) = 1/1 + 2/2 + 3/1 + 4/4
• f (2) = 1 + 1 + 3 + 1
• f (2) = 6

Given N, find f (N)!

Simplified formula that I found using Wolframalpha, finding the first 10 elements: (4 ^ (n + 1) + 8) / 12

Code:

``````#understand
#define MOD 1000000007
using namespace std;
typedef short i16;
typedef unsigned short u16;
typedef int i32;
typedef unsigned int u32;
typedef long int i64;
typedef unsigned long int u64;
typedef float f32;
typedef double f64;

u64 pawa (u64a, u64b) {
u64 tot = 1;
for (u64 i = 0; i < b; i++) {
tot *= a;
tot = tot % MOD;
}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
u64 n;
cin>> n;
cost << (pawa (4, n + 1) + 8) / 12 << & nbsp ;;
returns 0;
}
``````

I have implemented these codes above and still get time limit exceeds. The constraint of the upper corner is 10 ^ 9. How can I improve my algorithm? Can you give me a hint or something?