FLOORI4 - Editorial

editorial
, , , ,
21

It’s the other way round it is when we divide a by m than b is the remainder.

22

Can anyone explain the sumfour(lli s) function in setter’s solution, what is the logic to find that sum?

23

Put s= 30t+y , expand s*(s+1)(2s+1)(-1+3s+3s^2)/30 , you will get what i did :smiley: , a brute way of thinking if you stuck with overflows :stuck_out_tongue:

24

I implemented the same thing in JAVA and got TLE using Big integer…Can anyone justify why? … here’s the code http://www.codechef.com/viewsolution/4768201

25

#include
#include <stdio.h>
#include <stdint.h>

using namespace::std;

int64_t power_sum(int64_t n, int64_t m)
{
m *= 30;
n %= m;

int64_t ans = 1;
ans = (ans * n) % m;
ans = (ans * (n + 1)) % m;
ans = (ans * (2 * n + 1)) % m;
ans = (ans * ((3 * n * n + 3 * n- 1) % m)) % m;

ans /= 30;
return ans;

}

int main()
{
int T;
scanf("%d", &T);

for (int t = 0; t < T; t++)
{
	int64_t N, M,A,B,C,y,z,ans,x,sum;
	scanf("%lld", &N);
	scanf("%lld", &M);

	 ans = 0;
	 sum=0;
	 x = 1;

	while (x <= N)
	{
		 y = N/x;
		 z = N/y;

		 A = power_sum(z, M);
		// cout<<"a-->"<<A<<endl;
		 B = power_sum(x - 1, M);
		// cout<<"b=="<<B<<endl; 
		 C = (A-B ) % M;
	//	 cout<<"---"<<C<<endl;
		C = (C * y) % M;
	//	cout<<C;

		sum= (sum + C) % M;

		x = 1 + z;
	}

	printf("%d\n", (int)sum);
}

return 0;

}

26

@achaitanasai i am also eager to know why this is working…

27

this much googling and logical thinking is for you to do.

28

@tonynater
Thanx for the explanation.

29

@war_lock just google it and find the standard definition of modulo.

30

why wrong answer
in it
#include<stdio.h>
int main()
{
int m,t;
long long n,i,sum=0;
scanf("%d",&t);
while(t–)
{
scanf("%lld%d",&n,&m);
for(i=1;i<=n;i++)
{
sum=(sum+(iiii)(n/i))%m;
}
printf("%lld\n",sum);
}
return 0;
}

31

why wa
http://www.codechef.com/viewsolution/4816078

32

But here in your example the different values for [n/i] should be 5(sqrt(25)) but its actually 9. so how it proves the statement?

33

There would be 2*sqrt(n) - 1 different values…and to get them quickly we do it in 2 steps.
first go from i=1 to i=sqrt(n) and sum the terms i^4 * (n/i)…basically brute force over sqrt(n) values.
next you will see that as i gets bigger, the (n/i) starts repeating for many consecutive i’s and it will be in range sqrt(n) to 1…so too take advantage of this fact we do a little reverse thing. say x = (n/i), we iterate over x from sqrt(n) to 1 and try to find how many i’s might give this value x…again this will be done in o(sqrt(n))…so total complexity remains o(sqrt(n)).

2 Likes
34

thanx @achaitanyasai for the trick.

35

The problem is that you have not reset the value of sum=0 for each test case…secondly this method will give tle

36

this trick is great however i couldn’t think of it so i just divided the numerator by 30 then used fmod , and that worked too.

37

When the number gets big, double loses precision and hence you do not get right answer also the your code is too slow to get AC

38

so, It always replaces the modular inverse ??

39

What is the proof of this statement that there are only sqrt(n) different values for [n/i] over all i from 1 to n.?

40

@akshul

HI…

there are at most 2 * sqrt(n) [upper bound] different value for all [n/i] over all i from 1 to n.

As we know if a i number is multiple of n than there are two number i ans (n/i) such that

i * (n/i)=n

As we know here one factor is less than or equal to sqrt(n) and other one factor is greater than or equal to sqrt(n) .

If you are taking i is first factor(less or equal to sqrt(n) ) than i can only have value from 1 to sqrt(n) and other one can have value from sqrt(n) to n;

i.e if a belong to [1 to sqrt(n)] total value that a can have, are sqrt(n).

if n is prefect square than one number will come twice sqrt(n)

that’s why total number sqrt(n)+sqrt(n)-1(to avoid repeating number)

if n is not perfect square of any number than can have at most 2*sqrt(n) factor.

HAPPY CODING