Advertisement
Saleh127

Spoj DCEPC11B / Wilson number Theory

Jul 4th, 2022
1,229
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None
  1. /***
  2.  created: 2022-07-05-03.46.15
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10. template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
  11. #define ll long long
  12. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  13. #define get_lost_idiot return 0
  14. #define nl '\n'
  15.  
  16. ll bigmod(ll a,ll c,ll d)
  17. {
  18.     ll ans=1ll;
  19.  
  20.     while(c>0)
  21.     {
  22.         if(c&1) ans=(ans*a)%d;
  23.         a=(a*a)%d;
  24.         c>>=1;
  25.     }
  26.  
  27.     return ans;
  28. }
  29.  
  30. int main()
  31. {
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie(0);
  34.     cout.tie(0);
  35.  
  36.     test
  37.     {
  38.         ll n,m,i,j,k,l,p;
  39.  
  40.         cin>>n>>p;
  41.  
  42.         if(n>=p)
  43.         {
  44.             cout<<0<<nl;
  45.         }
  46.         else
  47.         {
  48.             ll ans=p-1;
  49.  
  50.             for(i=n+1;i<p;i++)
  51.             {
  52.                 ans*=bigmod(i,p-2,p);
  53.                 ans%=p;
  54.             }
  55.  
  56.             cout<<(ans+p)%p<<nl;
  57.         }
  58.     }
  59.  
  60.  
  61.  
  62.     get_lost_idiot;
  63. }
  64.  
Advertisement
RAW Paste Data Copied
Advertisement