plz help me!!!
The first thing that you have to notice is that the max value for f(n)= n%i%j%k%n is (n-1)/2.
as the max value is less than n, The expression can be changed to n%i%j%k=m
Let’s denote the max value by m.
Now it can be proved that if n%i==m then i=m+1;
Now there are multiple cases.
- n%i==m Then the values that i can take will be m+1. And j, k can each take values >m and <=p. thus this case results in 1(p-m)(p-m) number of ways.
- n%i==n and n%j==m. then i can take the values n+1,n+2,…p. these are p-n values. similar to first case, j=m+1. Therefore j can take only 1 value. and i can take p-m values. making the total to be (p-n)1(p-m);
- the third case is n%i==n and n%j==n and n%k==m. Proceeding in previous ways, toatl will be (p-n)(p-n)1;
Adding up all these cases will give the answer. Also the corner case of n<=2 is explained well in editorial.
Let’s write that equation out:
score = (((N\mod i)\mod j)\mod k)\mod N
The first thing to note are the special cases where N is 1 or 2. In these cases, the maximum possible score is 0 and all possible values of i,j,k get that score. So the answer is P^3.
Next, exactly one of the variables i,j,k must have an effect. N \mod N = 0, which is not good, but on the other hand if N \mod i < N, then the \mod N part will not reduce the score, so the \mod j and \mod k parts shouldn’t either.
So we are looking for one ideal modulus x that changes the score to the highest possible value. This x=N/2+1. It is the smallest possible x such that floor(N/x)=1.
Now, to work out how many ways to achieve the optimum score.
Let’s suppose N=34, P=47
x = 34/2+1 = 18
The highest possible score is 34 \mod 18=16. There are two possible scores that matter, 16 and 34, and for each score we track the total number of ways to get that score:
__________|__16__|__34__ Initially | 0 | 1 After %i | 1 | 13 After %j | 44 | 169 After %k | 1533 | 2197 After %N | 1533 | 0
There are P-N=13 different values of i,j or k that do not change the score if it is 34, so the number of ways to get a score of 34 increases by a factor of 13 each time.
Tracking the ways to get a 16 score is slightly more complicated. There are 47-16 = 31 values of j or k that will not change an existing score of 16. There is also 1 value that changes a 34 to a 16. Taking the “After %j” line for example, we read from the line above and there is 1*31 ways that a 16 score can remain a 16 score, and 13*1=1 way that a 34 score can become a 16 score.
how to identify max value ie…(n-1)/2