Changing complexity from O(n) to O(1)

[SlashGeek]

For the following code :

 s = 0 ;
 for(i=m ; i<=(2*n-1) ; i+=m)
      {
            if(i<=n+1)
            { s+=(i-1)/2 ; }
           else
            { s+=(2*n-i+1)/2 ; }  
      }
 

I want to change the complexity of the code from O(n)
to O(1) . So I wanted to eliminate the for loop . But as
the sum "s" stores values like (i-1)/2 or (2*n-i+1)/2 so eliminating the loop involves tedious calculation of floor value of each (i-1)/2 or (2*n-i+1)/2 . It became very difficult for me to do so as I might have derived the wrong formula in sums of floors . Can u please help me in Changing complexity from O(n) to O(1). Or please help me with this floor summations . Is there any other way to reduce the complexity ? If yes ... then how ?

[Rabbit]

I don't understand what your goal is. What is the code supposed to do?

[SlashGeek]

this is my whole code :

 
#include<stdio.h>
int main()
{
   unsigned long int t , n , m , i ;
   unsigned long long int s ,s1 ;
   scanf("%ld",&t);
   while(t--)
   {   s = 0 ;
      scanf("%ld",&n) ;
      scanf("%ld",&m) ; 
      for(i=m ; i<=(2*n-1) ; i+=m)
      {
            if(i<=n+1)
            { s+=(i-1)/2 ;  }
           else
            { s+=(2*n-i+1)/2 ; }  
      }
      printf("s=%lld\n",s); 
   }
   return 0 ;
}
 

Given N and M I wanted to calculate how many pairs a,b(1 <= a < b <=N) are there such that (a+b) is divisible by M . For example when N=4 and M=3, there are 2 possible pairs the sum of which is divisible by M and they are (1,2) and (2,4).

I m using for loop to calculate the sum . I want to eliminate the for loop so that I can calculate the sum in O(1) complexity . So I wanted to derive a formula which would calcutate the sum directly without using for loop . As the sum stores the values like (i-1)/2
I have to calculate the summation of the floor values of (i-1)/2 for (i<=n+1) and summation of the floor values of (2*n-i+1)/2 for (i>n+1) . It became very tedious job as I m uncomfortable with this foor sum . So the formula I derived for summation is not working properly . Can u plz help me out with this problem ? I just want to eliminate the loop so that it can work for larger inputs . Is there any other way to reduce the complexity ? If there is any other way then please elaborate that if I want to eliminate loops what procedure should I follow for future references ?

[donbock]

You are seeking a closed-form expression; also called an analytical solution. This is more of a mathematics problem than a programming problem. Perhaps this wikipedia article can help: Closed-form expression. If you derive a formula then I would check it out with paper and pencil before trying to write a program for it.

What do you mean by the term floor value?

You say "I have to calculate the summation of the floor values of (i-1)/2 for (i<=n+1) and the summation of the floor values of (2*n-i+1)/2 for (i>n+1)." You identified two summations, but only one limit for each. Typically a summation goes from one limit to another in discrete steps. What are the limits and step size you want?

By the way, pedantically speaking, it is possible for an O(1) program to contain a for-loop ... as long as the number of times through the loop is indepedent of the input values. This is a harsh condition that makes it hard to imagine a practical use of a for-loop in an O(1) program.