Advertisement
Saleh127

Light OJ 1170 / Catalan Num Combi

Jan 18th, 2022
1,012
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-19-00.24.14
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11. map<ll,ll>y;
  12. vector<ll>x;
  13. ll mod=1e8+7;
  14. ll f[100005];
  15.  
  16. ll bigmod(ll a,ll c,ll d)
  17. {
  18.     if(c==0) return 1LL;
  19.     ll x=bigmod(a,c/2,d);
  20.     x=(x*x)%d;
  21.     if(c%2==1LL)
  22.     {
  23.         x=(x*a)%d;
  24.     }
  25.     return x;
  26. }
  27.  
  28. void fact()
  29. {
  30.     ll i;
  31.     f[0]=1;
  32.     for(i=1; i<=100000; i++)
  33.     {
  34.         f[i]=(f[i-1]*i)%mod;
  35.     }
  36. }
  37.  
  38.  
  39. void sqr()
  40. {
  41.     ll i,j;
  42.  
  43.     for(i=2; i<=100002; i++)
  44.     {
  45.         j=i*i;
  46.         while(j<=(ll)(1e10))
  47.         {
  48.             if(y[j]==0) x.push_back(j);
  49.            
  50.             y[j]=1;
  51.  
  52.             j*=i;
  53.         }
  54.     }
  55.    
  56.     sort(x.begin(),x.end());
  57. }
  58.  
  59. ll nCr(ll n)
  60. {
  61.     ll ans=(f[2*n]);
  62.  
  63.     ll inv = bigmod((f[n]*f[n+1])%mod,mod-2,mod);
  64.  
  65.     ans=(ans*inv)%mod;
  66.  
  67.     return ans;
  68.  
  69. }
  70.  
  71. int main()
  72. {
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0);
  75.     cout.tie(0);
  76.  
  77.     fact();
  78.     sqr();
  79.  
  80.     test
  81.     {
  82.         ll n,a,b,i,j;
  83.  
  84.         cin>>a>>b;
  85.  
  86.         n=(upper_bound(x.begin(),x.end(),b)-x.begin())-(lower_bound(x.begin(),x.end(),a)-x.begin());
  87.  
  88.         cout<<"Case "<<cs<<": ";
  89.  
  90.         if(n==0)
  91.         {
  92.             cout<<0<<nl;
  93.         }
  94.         else
  95.         {
  96.             cout<<nCr(n)<<nl;
  97.         }
  98.     }
  99.  
  100.     get_lost_idiot;
  101. }
  102.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement