You are not logged in. Please login at www.codechef.com to post your questions!

×

Help me with my code for WITMATH

I submitted my code in python of WITMATH during the contest and got AC. When i was submitting the same using C++ it was giving TLE though i had taken all steps to prevent overflow. Please can anyone help. Here's my code:

/*aayushagarwal*/
#include<cstdio>
#include<cstdlib>
using namespace std;
unsigned long long int mult(unsigned long long int a,unsigned long long int b,unsigned long long int c)
{
      unsigned long long int x=0,y=a%c;
      while(b>0)
      {
            if(b%2==1)
            {x=x+y;
                  if(x>c)x=x%c;
            }
            y=y+y;
            if(y>c)y=y%c;
            b/=2;
      }
      return x%c;
}
unsigned long long int modulo( unsigned long long int a, unsigned long long  int b, unsigned long long  int c)
{
      unsigned  long long int x = 1;
      unsigned long long int y = a;
      while (b>0)
      {
            if (b%2==1)
                  x = mult(x,y,c);
            y = mult(y,y,c);
            b = b/2;

      }
      return x%c;
}


bool millerRabin(unsigned long long int N,unsigned long long int iteration)
{
      if (N<2)
            return false;
      if (N!=2&&N%2==0)
            return false;

      unsigned  long long int d=N-1;
      while (d%2==0)
            d = d/2;

      for (long long int i=0;i<iteration;i++)
      {

            unsigned long long int  a = rand()%(N-1)+1;
            unsigned long long int temp = d;
            unsigned long long int x = modulo(a,temp,N);
            while (temp!=N-1 && x!=1 and x!=N-1){
                  x = mult(x,x,N);
                  temp = temp*2;
            }

            if (x!=N-1 && temp%2==0)
                  return false;

      }
      return true;
}
int main()
{   
      unsigned long long int n;int t;

      scanf("%d",&t);
      while(t--)
      {
            bool prime=false;
            scanf("%llu",&n);
            if(n==2||n==3)
                  printf("%llu\n",n);
            else if(n==4)
                  printf("3\n");
            else if(n==5||n==6)
                  printf("5\n");
            else if(n==7||n==8||n==9||n==10)
                  printf("7\n");
            else if(n==11||n==12)
                  printf("11\n");

            else
            {
                  while(!prime)
                  {       
                        if(n%2!=0 && n%3!=0 && n%5!=0 && n%7!=0 && n%11!=0)
                              prime=millerRabin(n,20);
                        n--;
                  }
                  printf("%llu\n",n+1);
            }
      }

      return 0;
}

asked 15 May '13, 19:04

aayushagarwal's gravatar image

2★aayushagarwal
2993510
accept rate: 0%

edited 17 May '13, 16:36

admin's gravatar image

0★admin ♦♦
19.8k350498541


Kindly post your question on the editorial page of the respective problem here: http://discuss.codechef.com/questions/9723/witmath-editorial. You will get your answer to your query.

link

answered 15 May '13, 19:26

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×16

question asked: 15 May '13, 19:04

question was seen: 825 times

last updated: 17 May '13, 16:36