vohrab1896's blog

By vohrab1896, history, 6 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it