11287 - Pseudoprime Numbers

[WingletE]

I got wrong answer.

Could anyone give me some test case? Or tell me where I should be more careful of.

Thanks.

[Jan]

Did you use 64 bit int (i.e long long in C)?

[WingletE]

Yes, I did.

I counted the first 3401 primes(the ones that smaller than 31624), and then checked if p is a prime. If not, then I checked if a^p mod p is equal to a.

This is my function:

Code: Select all

long long BigMod(long long a, long long n, long long p)
{
    if(n == 1)  return a % p;
    else if(n % 2 == 0)  return square(BigMod(a, n/2, p)) % p;
    else return square(BigMod(a, n/2, p))*(a % p) % p;
}
long long square(long long k)
{
    return k * k;
}

Is there any wrong?

[mmonish]

I think u got WA bcoz of integer overflow.
Better u can use this function as Bigmod..

Code: Select all

long long Bigmod(long a,long b,long n)
{
	long long c=0,d=1,k=0;
	long arr[70];
	while(b)
	{
		arr[k++]=b%2;		
                        b/=2;
	}
	while(k--)
	{
		c=2*c;		
                        d=(d*d)%n;
		if(arr[k]==1)
		{
			c=c+1;			
                                    d=(d*a)%n;
		}
	}
	return d;
}

Hope this helps.

[goodwill]

In the case where n is odd, it should be :

Code: Select all

return (square(BigMod(a, n/2, p))%p)*(a % p) % p; 

[WingletE]

To mmonish:
Your right. It must be overflow.
I looked your Bigmod. It's a good method, but I don't understand what the use of 'c' in your Bigmod.

To goodwill:
I adapted my BigMod and got accepted.



Thanks to you all.:):)

[mmonish]

>>WingletE

C can be avoided to compute the Bigmod.
Here c has used to count the current power status.

[WingletE]

Thanks! I got it.

[abcman13]

hey guys, any suggestions on what i could do to correct my code?

Code: Select all

#include <stdio.h>
#include <math.h>

long long int a,p;
int prime[40000],arr[40000];

long long int sq(long long int n);
long long int mod(long long int m);
int isprime();

int main()
{
     int l,i,j,k,f;
     long long int q;
     for(i=3,prime[1]=2,f=2;i<31624;i+=2)
          if(arr[i]==0)
          {
               for(j=i*i,k=2*i;j<31624;j+=k)
                    arr[j]=1;
               prime[f++]=i;
          }
     prime[f]=1000000001;
     while(scanf("%lld %lld", &p,&a)&&p)
     {
          if(isprime())
          {
               printf("no\n");
               continue;
          }
          a%=p;
          q=mod(p-1)%p;
          if(q==1)
               printf("yes\n");
          else
               printf("no\n");
     }
     return 0;
}

int isprime()
{
     int i,l;
     if(p<31624)
          return !arr[p];
     for(i=1,l=(int)sqrt(p)+1;prime[i]<l;i++)
     {
          if(p%prime[i]==0)
               return 0;
     }
     return 1;
}

long long int sq(long long int n)
{
     n%=p;
     return (n*n)%p;
}

long long int mod(long long int m)
{
     if(m==1)
          return a;
     if(m%2)
          return (a*(sq(mod(m/2))))%p;
     return sq(mod(m/2));
}

[brianfry713]

Input:

Code: Select all

131877361 55808896
0 0

AC output:

Code: Select all

yes

[richatibrewal]

Hii, I am not getting the required output for uva 11287, Plz help:

Code: Select all

#include<cstdio>
#include<cmath>
#include<vector>

using namespace std;
vector<long int> m(31655,1);
long int temp;
long int power(long int a,long int po,long int p)
{
    if(p==0)
        return 1;
    else if(p%2 == 0)
    {

        temp=(power(a,po,p/2)*power(a,po,p/2))%po;
    }
    else
    {
        temp=(power(a,po,(p-1)/2)*power(a,po,(p-1)/2)*a)%po;
    }
    return temp;
}
int main()
{
    long int a,p,u,flag,arr[50],num,k,i,j,mod[10000];
    m[0]=m[1]=m[31644]=m[31645]=0;
    for(i=2;i<=31655;i++)
    {
        u=pow(i,0.5);
        for(j=2;j<=u;i++)
            if(i%j == 0)
            {
                 m[i]=0;
                 break;
            }
    }
    while(scanf("%ld%ld",&p,&a)!=EOF)
    {
        if((a==0)&&(p==0))
            break;
        flag=0;
        u=pow(p,0.5);
        for(i=2;i<=u;i++)
        {
            if(m[i])
            {
                if(p%i==0)
                {
                    flag=1;
                    break;
                }
            }
        }
        if(!flag)
        {
            printf("no\n");
            continue;
        }
        u=power(a,p,p);
        if(u==a)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

[brianfry713]

It looks like you figured it out.