Getting WA in CHFING-codechef

Revision en2, by vohrab1896, 2019-06-18 07:14:02

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English vohrab1896 2019-06-18 07:18:21 36
en3 English vohrab1896 2019-06-18 07:16:36 2 Tiny change: 'h>\n\n\n\n\n\nusing ' -> 'h>\n\n\n\n``\n\nusing '
en2 English vohrab1896 2019-06-18 07:14:02 8 Tiny change: 'c++.h>\n\nusing ' -> 'c++.h>\n\n\n\n\n\nusing '
en1 English vohrab1896 2019-06-18 06:42:55 1508 Initial revision (published)