Problem 4:Regions in n-gon

Points:

Small Case: 8 Answer: 246

Large Case: 16 Answer: 1259

Given a polygon of n vertices with each vertex pair connected by a straight line,let m be the maximum number of distinct regions inside it.

The problem is to find m mod 9997

For e.g. for n=5

number of regions = 11

Small Case: n=10

Large Case: n=11111

Solution:

For n vertices the number of regions formed are given by the relation
C(n,4) + C(n,2) - n + 1
where C(n,r) = n! / ((n-r)!*r!)

Reference:N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995

Code:

#include<iostream>
#include<cmath>
using namespace std;
#define x 9997
int primes[19999]={2,3,5,7,11,13,17,19,23};

int ncr(int n,int r)
{
   int a,b,c,d,e,f,prod,temp,i;
   a=n;
   b=r;
   c=n-r;
   prod=1;
   for(i=0;primes[i]<=a;i++)
   {
      d=e=f=0;
      long long pr1=1,j;
      temp=primes[i];
      while(a/temp != 0)
      {
         d+=a/temp;
         e+=b/temp;
         f+=c/temp;
         temp=temp*primes[i];
      }
      temp=primes[i];
      for(j=1;j<=(d-e-f);j++)
         pr1=(pr1*temp)%x;
      prod=(prod*pr1)%x;
   }
   return prod;
}


int main()
{
   long long n=9,k,prod=1,i,temp,t;
   float check;
   bool flag=false;
   for(i=25;i<=11130;i+=2)
   {
      check=sqrt((double)i);
      for(k=0;primes[k]<=check;k++)
      {
         if(i%primes[k]==0)
         {
            flag=false;
            break;
         }
         else
            flag=true;             
      }
      if(flag==true)
         primes[n++]=i;          
   }
   cin>>t;
   while(t--)
   {
      int nc4,nc2,ans;
      cin>>n;
      nc4 = ncr(n,4);
      nc2 = ncr(n,2);
      ans = ((nc4+nc2-n+1)%x + x)%x;
      cout<<ans<<endl;
   }
}