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