Hi CF community! I have been solving this problem(https://www.codechef.com/JUNE19B/problems/CHFING) from quite a few days. Previously, I didn't know about Frobenius Numbers and then I solved this using it but still getting Wrong Answer. Here is my code
#include<bits/stdc++.h>
using namespace std;
long long fast_pow(long long base, long long n,long long M)
{
if(n==0)
return 1;
if(n==1)
return base;
long long halfn=fast_pow(base,n/2,M);
if(n%2==0)
return ( halfn * halfn ) % M;
else
return ( ( ( halfn * halfn ) % M ) * base ) % M;
}
long long findMMI_fermat(long long n,long long M)
{
return fast_pow(n,M-2,M);
}
int main()
{
int t;
long long n,k;
cin>>t;
while(t--)
{
long long a=1000000007;
cin>>n>>k;
if(k==1)cout<<"0"<<endl;
else
{
long long l=findMMI_fermat(n-1,a);
long long f=(((((((k-2)%a)*l)%a)*(k%a))%a+k)%a-1)%a;
if(f<(k))cout<<(k-1)%a<<endl;
else
{
long long count=0;
long long l1=findMMI_fermat(k,a);
long long f1=((f+1)%a*(l1%a))%a;
long long f2;
f2=(((((f1-1)%a)*(f1)%a)%a)/2)%a;
count=((((f2%a)*((n-1)%a))%a+f1)%a-1)%a;
cout<<(f%a-(count)%a+a)%a<<endl;
}
}
}
return 0;
}
Also, I have a doubt in using Fermat's Theorem. In (a/b)%m, if a is not divisible by b, it is giving a large number than expected. Maybe I am somewhere wrong in my concept. Please help if possible. Thanks.
Auto comment: topic has been updated by vohrab1896 (previous revision, new revision, compare).
Auto comment: topic has been updated by vohrab1896 (previous revision, new revision, compare).
Auto comment: topic has been updated by vohrab1896 (previous revision, new revision, compare).
I believe the problem lies in where you wrote
You cant just divide by two. You need to calculate the modular inverse of it first.
Or he could have divided the number by 2 first and then apply the mod
Still WA after changing it to this- long long l2=findMMI_fermat(2,a); f2=(((((f1-1)%a)*(f1)%a)%a)*l2%a)%a;
It would be better if you shared your thought process too.
For example I did it like this,
Say a "step" is using all the numbers we have in hand, to make new numbers. If initially we have the values in $$$[k, k + n - 1]$$$ then at second step it will be $$$[2k, 2(k + n - 1)]$$$. And at $$$x$$$ th step it will be $$$[xk, x(k + n - 1)]$$$. Now we need to find a $$$x$$$ for which $$$x(k + n - 1) + 1 >= (x + 1)k$$$ meaning that there is no missing values between $$$x$$$ th and $$$(x+1)$$$ th step. Solving the inequality you will get $$$x = \left \lceil \frac{k - 1}{n - 1} \right \rceil$$$
Now all that remains is to calculate this sum, $$$\sum_{i = 1}^{x - 1} \Big( (i+1)k - i(k+n-1) - 1 \Big)$$$ which can be simplified to, $$$(x-1)(k -1) + \frac{x(x-1)(1-n)}{2}$$$ and lastly, we will need to add $$$k - 1$$$ to the answer because anything before $$$k$$$ isnt reachable.
Sorry for that. Basically, the idea is first to calculate the last non-representable number which can be obtained from [k,k+n-1] and then remove all the representable numbers from it. So the last non-representable number can be obtained using frobenius number which is f in my case. This f will be less than k when xk belongs to [k,k+n-1]. So, in that case, k-1 is the total number of non-representable numbers. Otherwise, I will calculate all the numbers which are representable. The number next to f is a multiple of k or f1*k(in my case). So, for all x less than f1, I am calculating the lengths [k,k+n-1],[2k,2(k+n-1)],[3k,3(k+n-1)] and so on. To calculate the sum of this series - (1*(n-1)+1)+(2*(n-1)+1)+(3*(n-1)+1) .... (this sum is count in my case) Atlast, subtracting this count from f gives me the answer.
The thing is you are moding the value of $$$f$$$ at first. And then you are checking if(f < k), so if $$$k$$$ is bigger than MOD then this will turn out to be WA. you need to preserve the actual value of f till that condition.
And if you try putting $$$n = 2, k = 10^{18}$$$ you will see that the value of $$$f$$$ actually overflows long long. So it is better to not calculate the sum in the way you are doing right now. Instead of calculating the value of $$$f$$$ explicitly, try using the values of f1 (the number of steps you sum goes) and other values, which are much smaller.
But your idea is correct (you can try the same idea on python btw).
1 5 13
The output for this case should be 24. But it is returning some large value. Basically, the returned value by modular division is larger which leads to wrong answer in this case. This is what I noticed- In (a/b)%m, if a%b is 0, then the value returned is correct but it returns a larger value otherwise.
In (f<k), I also tried (f<k%a), but this failed too.
Obviously you will get some larger value. It isn't really any random value. you know that if there is a number $$$x \neq 0$$$, then there exists another number $$$y$$$ such that $$$x.y = 1$$$. This $$$y$$$ is called multiplicative inverse.
When you talk about multiplicative inverse of $$$x$$$ modulo some $$$M$$$ it means a number $$$y$$$ such that after multiplying it with $$$x$$$ and moding by $$$M$$$ you get 1, basically, $$$x.y \equiv 1 (mod M)$$$
Now when (a/b) is a fraction, you are getting a somewhat random number, but that isnt really random. It is actually the integer value of that fraction. If you just multiply that number with b and mod the result, you will see that you get back a. Because a * b * inv(b) = a * 1 = a.
and lastly, f < k % a won't work for obvious reasons -_-. you can check my solution, pretty much the same thing, but there are no values that would overflow.
(a/b)%m means the number c such that (c*b)%m=a%m. To calculate this you need to compute inverse modulo of b i.e c= (a*inverse(b))%m and inverse of b is (b^(MOD-2))%MOD (this comes from fermat's theorem).