 # FLOORI4 - Editorial

#1

Problem link : contest practice

Difficulty : Easy

Pre-requisites : AD-hoc problems experience

Solution :

At first, the formula for the sum of 14+24+…+n4 is n(1+n)(1+2n)(-1+3n+3n2)/30. The level of the problem is EASY, so the formula can be found on the internet.

At second, there are only sqrt(n) different values for [n/i] over all i from 1 to n. This fact is also well known and can be proved.

So, the solution is as follows:

• We iterate all the different values of [n/i].
• For each such value X we can calculate the maximal range [L; R] such that for each i, L <= i <= R, [n/i] = X. When we have a segment, we can calculate an answer for it, using the above formula in O(1).

So the total time complexity is O(sqrt N) per a test case.

Setter’s solution: link

Tester’s solution: link

#2

Why the same implementation in python gave TLE, but worked in java,cpp ?

#3

Links to the setter and tester solution don’t work!

#4

Can anyone please explain how does the “multiplying m by 30 and then dividing result by 30” approach works??

#5

Can anyone please explain what is wrong with this approach? And isn’t the formula for (1^4)+(2^4)+…, while we need to calculate (1^4)(n/1) + (2^4)(n/2) +…?

#include<stdio.h>

#include

#include<math.h>

using namespace std;

int main()

{

``````unsigned int n_of_tst,i,j,nbyi;

long double n,m,ans={0};
cin>>n_of_tst;

for(i=0;i<n_of_tst;i++)
{
cin>>n>>m;
for(j=1;j<=n;j++)
{
nbyi=n/j;
ans*=ans*+(pow(j,4)*nbyi);
}

}
for(i=0;i<n_of_tst;i++)
{
cout<<(int)ans*%(int)m<<endl;
}

return 0;
``````

}

#6

Same solution in Ruby gives TLE. Codechef team should seriously consider increasing the time limit for slower languages for such problems.

#7

I did the same in Python and was getting TLE…!!!

#8

Can some please explain me this
there are only sqrt(n) different values for [n/i] over all i from 1 to n

eg: n= 25
I get different values of floor(n/i), they are as follows

i
1 25,
2 12,
3 8,
4 6,
5 5,
6 4,
7 3,
8 3,
9 2,
10 2,
11 2,
12 2,
13 1,
14 1,

so different values are 25, 12, 8, 6, 5, 4, 3, 2, 1

#9

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

#10

#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
``````

", (int)sum);
}

``````return 0;
``````

}

#11

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
",sum);
}
return 0;
}

#12

#13

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.?

#14

@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

#15

The picture is no longer visible!

#16

I always observe that for last 3-4 problems in each contest we don’t find a single Python submission and for editorial approach also we get tle, so codechef should increase time limit for Python or provide a Python solution or remove Python option for such problem statements.

#17

all right … the part I got stuck at was dividing it by 30. Since M is given as input, what is the guarantee that the modulo inverse of 30 exists ?

#18

@krooonal You can play a trick as : just multiply ‘m’ with ‘30’.Say this as M.i.e M=m*30;now perform modulo using M.Finally divide the anser with 30.Refer my solution : http://www.codechef.com/viewsolution/4803010 .POWER() method in my solution #19

@achaitanyasai You just changed my life. Now i think that my whole life has been a lie man, i spent 4 hours thinking about that and still coudn’t get a right answer Thanx for the help, man!

#20

It seems out of 696 solutions for this problem, none were in Python 2/3. This does not seem fair…