Mercuto's blog

Doubt in using primes for modular operations.
By Mercuto, history, 4 years ago, In English

I have written program for printing catalan numbers.

With smaller primes output is correct, but with larger primes output is coming out to be incorrect. I am not able to figure out why.

Here is code :

#include<bits/stdc++.h>
using namespace std;

typedef long long int   ll;
#define int             ll

//some primes
int p1=1e9+7;
int p2=2097593;
int p3=6643838879;
int p4=5600748293801;

int mod=p2;

int mul(int a,int b){
    return ((a%mod)*(b%mod))%mod;
}

int binpow(int a,int b,int mod){
    a=(a%mod+mod)%mod;
    int res=1;
    while(b>0){
        if(b%2){
            res=mul(res,a);
            b--;
        }
        a=mul(a,a);
        b/=2;
    }
    return res%mod;
}

int fac[100000];
void init(){
    fac[0]=1;
    for(int i=1;i<100000;i++){
        fac[i]=mul(fac[i-1],i);
    }
}

signed main(){
    init();
    for(int n=0;n<=10;n++){
        cout<<n<<" : ";
        int x=fac[2*n];
        x=mul(binpow(fac[n],mod-2,mod),x);
        x=mul(binpow(fac[n],mod-2,mod),x);
        x=mul(binpow(n+1,mod-2,mod),x);
        cout<<x<<endl;
    }
}

Thanks in advance.

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

»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

overflow when you multiply (if $$$(p-1)^2 > \texttt{max_int}$$$).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Can you please tell on which line overflow would occur.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      just replace int with long long everywhere, or read through it on your own if you want to understand more thoroughly (I think now you should know what to look for)

      as a hint, since I said "when you multiply" -- you can start by checking your mul method, which is one line long

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I got it. I have to implement mul() function differenty.

        I have already defined int as long long int, only problem is in mul() function.

        Thanks.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Ah, yeah, the problem is actually that $$$(p-1)^2 > \texttt{max_ll}$$$. That is a lot more annoying to fix. This is why contests typically use primes around $$$10^9$$$, so you don't have this issue.

          → Reply