Мне нужен какой-то эффективный appproach

---

О решении задачи ПРЛКМ:
SPOJ.com - проблема PRLCM[^]

Я использовал алгоритм O(n^2)
в течение 1 секунды я ищу какой-то более эффективный подход
Я был бы полезен, если бы кто-нибудь помог мне.

Что я уже пробовал:

#include <bits stdc++.h="">
#define ll long long int
#define f(i, a, b) for (us i = a; i < b; i++)
#define vi vector<us>
#define pb push_back
#define us unsigned long long int
#define endl '\n'
#define mod 998244353
#define mp make_pair
#define pi = 3.1415926535897932384626433
using namespace std;
us solve(us arr[], us);
us lcm(us, us);
us solve(us arr[], us n)
{
    us sum = 0;

    for (us i = 0; i < n - 1; i++)
    {
        for (us j = i + 1; j < n; j++)
        {
            sum = sum + lcm(arr[i], arr[j]);
        }
        sum = sum % mod;
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t = 1;
    while (t--)
    {
        us n;
        cin >> n;
        us arr[n];
        for (us i = 0; i < n; i++)
            cin >> arr[i];
        cout << solve(arr, n);
    }
    return 0;
}

us lcm(us x, us y)
{
    return ((x*y)/__gcd(x,y));
}

---