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.
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) +…?
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;
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;
}
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.
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.
@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 : CodeChef: Practical coding for everyone .POWER() method in my solution
@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!