# IOPC13B: Find the Sum

How to improve time in this problem so that it could have been accepted;

``````#include<stdio.h>
int scan(){
int t=0;
char c;
c=getchar_unlocked();
while(c<'0' || c>'9')
c=getchar_unlocked();
while(c>='0' && c<='9'){
t=(t<<3)+(t<<1)+c-'0';
c=getchar_unlocked();
}
return(t);
}

int main(void){
short unsigned M, N, temp, ans[100001], x, y=0;
short unsigned T;
scanf("%hu", &T);
temp=T;
//for(temp=0; temp<T; temp++){
while(T){
M=scan();
N=scan();
for(x=0; x<M; x++)
y = y + (x*N)/M;
ans[temp]=2*y;
T--;
}
//for(temp=0; temp<T; temp++)
while(temp){
printf("\n%hu", ans[temp]);
temp--;
}
return 0;
}``````

i think this question can’t be solved in this naive method, seeing the submissions for this question, there is this formula –

``````        (N-1)*(M-1)+ gcd(N,M)-1  which gives the sum of quotients.
``````

But i can’t figure out how we come up with this, it will be good if some one explains it.

Can Someone please explain how the sum of quotients is
`(N-1)*(M-1)+ gcd(N,M)-1 `
Thank you.

1 Like

I tried this, but for some reason it didn’t got accepted…
Don’t know what the error was, it gave correct answer on my pc, but said wrong answer when I tried to submit.

``````#include<stdio.h>
int main()
{
unsigned long long t;
unsigned long long m, n;
unsigned long long j;
unsigned long long rem;
unsigned long long quo;
unsigned long long ans;
scanf("%llu",&t);
for(j=0;j<t;j++)
{
scanf("%llu",&m);
scanf("%llu",&n);
quo = n/m;
rem = n%m;
ans = quo*(m-1)*m;
if(rem!=0)
ans+=(rem-1)*(m-1);
printf("%llu\n",ans);
}
return 0;
}``````
1 Like

same problem here buddy

The approach you used is Quite the obvious one!! And obvious solutions seldom get accepted… Here is the approach I used…
Consider N and M are relatively prime to each other :
Eg 7 5
The answer, if done by actual division rather than the integer division would give us…

(7/5)+(14/5)+(21/5)+(28/5) which is (7*(1+2+3+4))/5

But since we consider the integer division the expected answer would be (5/5)+(10/5)+(20/5)+(25/5)

So we are missing out on (7%5)+(14%5)+(21%5)+(28%5)/5, which is (2+4+1+3)/5

Which is nothing but (1+2+3+4)/5
So you find the actual answer and subtract the Sm-1/M value ,where
Sm-1 =Sum of first M-1 numbers
This works for relatively prime numbers.

If M divides N then the answer would be the actual answer

If the gcd(N,M) !=1, then a different approach is required

Consider 10 6

We would have to subtract (10%6+20%6+30%6+40%6+50%6)/6 , which is (4+2+0+2+4)/6.
You can use this explanation and derive at a formula.
Here is my solution

Another worthwhile point to note is : The answer for N,M and M,N is same

That is N=10 M=6 And N=6 M=10 ,is same…

Can you please explain how the gcd thing came up or atleast how you came up with closed expression when gcd is not 1.

@takalukia: It gives a problem “Time Limit Exceeded”. Please tell me how to optimize my code.

(N-1)*(M-1)+ gcd(N,M)-1
this formula is valid.

case:1

When N and M are coprimes then Ni and Nj cannot leave same remainder with M for 0<i,j<M-1.
If they leave the same remainder that implies that abs(N*(i-j)) is a multiple of M, as (i-j)<M hence N and M must have a common factor greater than 1. This contradicts our initial hypothesis that their g.c.d is 1.

case:2

Now for any N and M, let the gcd be g.

let N = g*k1 and M = g*k2.

g.c.d(k1,k2) should be 1.

The situation here is similar to the situation when N and M are coprimes.

For example lets consider N=10 and M=6 => g(gcd)=2 k1=5 k2=3.

The remainders we are going to get are 0 4 2 0 4 2.

0 4 2 is the repeating sequence. This can be rewritten as 0*g 1*g … (k2-1)*g because k1 and k2 are coprimes. There are k2 remainders in each such repeating sequence. As the total length is k2*g, hence there must be g such repeating sequences.

So in general the sum of the remainders is

sum_remainders = g*g*sigma[i from 0 to k2-1].

total_sum = N*sigma[i from 0 to M-1] is N*M*(M-1)/2.

We have to subtract the sum of remainders from total_sum to get the sum of quotients*M.

total_sum-sum_remainders = ((N-1)*(M-1)+g-1)/2.

Hence the proof.

3 Likes
//