Problem 2: Two units triangle

Points:

Small Case: 5 Answer: 28657704

Large Case: 10 Answer: 99997667

Given a triangle with a side of length 't' units and another side of length 't+1' units, it is specified that the altitude of the triangle on side of length 't' units is at distance of 2 units from centre of that side and the area of triangle is integer.
For e.g

Above figure shows first such triangle. It is a right angled triangle with side lengths 3 units,4 units and 5 units ,altitude 3 units and the area 6 units.

The sides of triangle are integers.

Small Case: N=15
Large Case: N=100000000

Solution:

From the constraints given in the problem, it can be proved that the 3rd side of the traingle has length 't-1', and the area of the traingle will be integral. Such traingles are called as 'Brahmagupta Traingle' and the altitute of such triangles follow the following recurrence relation : f(n)=4*f(n-1)-f(n-2), f(1)=3, f(2)=12 .

Reference:Raymond A. Beauregard and E. R. Suryanarayan, The Brahmagupta Triangles[1998].

Code:

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#define ll long long int
#define MAX 100000000ll
#define MOD 100000007ll
using namespace std;
ll pr[MAX]={0};
int main()
{
    ll i;
    pr[1]=1;
    pr[2]=4;
    for(i=3;i<=MAX;i++)
        pr[i]=((pr[i-1]<<2)%MOD-pr[i-2]%MOD+MOD)%MOD;
    printf("%lld\n",(3*pr[MAX])%MOD);
    return 0;
}