-3
\$\begingroup\$

I want to use only one for Loop for this code. Is this possible? If not then how can I optimise my code further?

It works well for the constraint 1 ≤ T ≤ 10, 2 ≤ N ≤ 10^3, 1 ≤ M ≤ 10^5, but I am getting time limit exceeded for 1 ≤ T ≤ 100, 2 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5.

#include <iostream>
using namespace std;
#include <vector>
#include <bits/stdc++.h>
#include <iterator>
#include <utility>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;

using namespace std;

int main() {
    // your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);   

    cpp_int t,ans;
    std::cin >> t;
    while(t-->0) {
    
        cpp_int n;
        std::cin >> n;
        
        cpp_int m;
        std::cin >> m;
        
        cpp_int count=0;
        
        for(int a=1;a<=n;++a) 
            {
                for(int b=1;b<=n;++b)
                {
                    
                    if(a<b) 
                     {
                       if( ((m%a)%b) == ((m%b)%a) )
                           count++;
                     }
            }
            }
            
            cout << count << "\n";
    }
    return 0;
}
\$\endgroup\$
4
  • 6
    \$\begingroup\$ Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How do I ask a good question?, as well as How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ May 10 at 17:45
  • 3
    \$\begingroup\$ This looks like a programming challenge, could you please include the text of the question and a link to the question? \$\endgroup\$ – pacmaninbw May 10 at 18:15
  • \$\begingroup\$ link \$\endgroup\$ – jerry00 May 11 at 3:33
  • \$\begingroup\$ Do you need to use boost::multiprecision::cpp_int or can you work with a regular integer type? The latter would likely be faster. \$\endgroup\$ – G. Sliepen May 11 at 6:40
2
\$\begingroup\$

I'm sure the puzzle intends you to use more math and less brute force. But here's a 2x speedup right away: Any loop of the form

for (int a=1; a <= n; ++a)  {
    for (int b = 1; b <= n; ++b) {
        if (a < b) {
            do something
        }
    }
}

can obviously be replaced with a loop of the form

for (int a=1; a <= n; ++a)  {
    for (int b = a+1; b <= n; ++b) {
        assert(a < b);  // compile with -DNDEBUG for speed
        do something
    }
}

(Also, notice my indentation and whitespace style changes. Adopt them in all the code you write.)

\$\endgroup\$
2
\$\begingroup\$

Don't write using namespace std;. You certainly don't need to write it twice!!

// your code goes here along with the duplicated using declaration makes me think that you did not really proof-read your own code first. Pay attention to what you're writing! It will go a long way to finding improvements and silly mistakes.

#include <bits/stdc++.h> is not a standard header. Some kind of implementation-specific header? Or is it internal details you are not supposed to use directly? Looking it up on Google, I see it's supposed to include all the standard headers... so why are you including others directly as well, and if it's supposed to be a precompiled header it needs to go first. Again, it looks like you're just pasting things together and not understanding or reviewing what you wrote.

cin.tie(NULL); Don't use the C macro NULL. C++ has a keyword nullptr now.

cpp_int t,ans; ans doesn't seem to be used anywhere, so why are you declaring it? See comments above. In general, don't define things ahead of their use, though the nature of cin>> I see why you are not initializing t. Generally don't declare more than one thing at a time.

std::cin >> t;
    while(t-->0)

So you loop counting down t until it reaches 0. You need t to be a arbitrary precision int because 64 bits isn't big enough?? If you are looping 2 to the 64 times, that would indeed take a long time. That's 1.8e19, and if each iteration took one nanosecond that's still on the order of ten billion seconds, or 317 years. So I seriously question your need to make t an extended precision integer and not a plain built-in 32-bit or 64-bit integer.

Likewise for count where you are counting up. Does your program run for hundreds of years? If not, 64 bit integers is enough!

Note for performance that % is a very slow operation.

\$\endgroup\$
1
\$\begingroup\$

Starting from Quuxplusone's answer, let's get rid of some more operations.

for(int a = 1; a <= n; ++a)
{
    for(int b = a + 1; b <= n; ++b)
    {
        if( ((m%a)%b) == ((m%b)%a) )
            count++;
    }
}

One thing to notice is that the quantity m%a never changes during the inner loop. So, we can move it to the outer loop.

for(int a = 1; a <= n; ++a)
{
    int ma = m%a;
    for(int b = a + 1; b <= n; ++b)
    {
        if( (ma%b) == ((m%b)%a) )
            count++;
    }
}

The next transformation relies on two facts:

  1. x % y < y for all positive integers x and y.
  2. x % y == x for all positive integers x and y if x < y.

So, since a < b, (m%a)%b == m%a. This allows us to write ma%b as just ma.

for(int a = 1; a <= n; ++a) 
{
    int ma = m%a;
    for(int b = a + 1; b <= n; ++b)
    {
        if( ma == ((m%b)%a) )
            count++;
    }
}

Now, we've reduced the number of modulo operations by nearly half. This comes after the reducing by half in the linked answer.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for your suggestion. But still time limit exceed is coming. \$\endgroup\$ – jerry00 May 11 at 5:17
  • 1
    \$\begingroup\$ What happens if you replace cpp_int with int? None of the numbers are big enough to require an arbitrary-precision integer type. \$\endgroup\$ – Mark H May 11 at 9:15
  • \$\begingroup\$ @jerry00 See above question. \$\endgroup\$ – Mark H May 11 at 9:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.