Click here to Skip to main content
15,035,685 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
On solving a problem PRLCM:
SPOJ.com - Problem PRLCM[^]

I used O(n^2) algorithm
for 1sec I'm looking for some more efficient approach
I would be helpful if someone help out.

What I have tried:

C++
#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));
}
Posted
Updated 13-Jul-20 7:26am
v2
Comments
Richard MacCutchan 13-Jul-20 10:54am
   
Remove the while loop, it serves no purpose.
Member 14849246 13-Jul-20 10:58am
   
ya! its a part of default competative code for multiple cases , other than that if you please help in algorithm like how to select all possible pairs and something like that
Richard MacCutchan 13-Jul-20 11:05am
   
Sorry, no idea, I stay well clear of those websites.

The idea of problems like this is that you work out an efficient algorithm to solve it, learning in the process how to analyse a problem and evaluate viable solutions.

Us doing that part for you turns it into a straight "convert this to code" problem and that isn't the point at all - you learn nothing about anything useful.

Like Richard, I don't go near such sites - the problems are well away from the real-world problems I n3eed to solve so they are of no real interest to me: but read the question carefully, and come up with a few different ways to do it manually - then evaluate them for efficiency.
   
Quote:
I used O(n^2) algorithm
for 1sec I'm looking for some more efficient approach

On first look, the problem is essentially O(N²), so optimizations are only marginally possible.
What is your problem with this code ?
   
Comments
Member 14849246 13-Jul-20 13:49pm
   
"constraints of the question"
it gives TLE on higher outputs

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900