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.
Please help, by correcting my code, ASAP. Anyone or ADMIN???
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
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
the answer would be 10/6+20/6+30/6+40/6+50/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.
Thanks for the answer.
@takalukia: It gives a problem “Time Limit Exceeded”. Please tell me how to optimize my code.
Let me answer how
(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.
2 Likes