如何优化，还是真的要写 ST 表

#include <iostream>
#include <algorithm>
using namespace std;
long long a, b, dp[5010][5010], p, q;
long long gcd(long long a, long long b)
{
    return !b ? a : gcd(b, a % b);
}
int main()
{
    cin >> a >> b;
    for(int i = 1; i <= a; i++) cin >> dp[i][i];
    for(int i = a - 1; i >= 1; i--)
    {
        for(int j = i + 1; j <= a; j++)
        {
            dp[i][j] = gcd(dp[i][i], dp[i + 1][j]);
        }
    }
    for(int i = 1; i <= b; i++) 
    {
        cin >> p >> q;
        cout << dp[p][q] << endl;
    }
}