11287 - Pseudoprime Numbers

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

11287 - Pseudoprime Numbers

Post by WingletE » Tue Sep 25, 2007 2:47 pm

I got wrong answer.

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

Thanks.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Sep 25, 2007 5:21 pm

Did you use 64 bit int (i.e long long in C)?
Ami ekhono shopno dekhi...
HomePage

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Wed Sep 26, 2007 3:42 am

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
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Wed Sep 26, 2007 4:19 am

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
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am

Post by goodwill » Wed Sep 26, 2007 5:31 am

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

Code: Select all

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

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Wed Sep 26, 2007 2:40 pm

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
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Wed Sep 26, 2007 3:29 pm

>>WingletE

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

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Thu Sep 27, 2007 8:28 am

Thanks! I got it.

abcman13
New poster
Posts: 6
Joined: Sun Apr 07, 2013 6:00 am

Re: 11287 - Pseudoprime numbers

Post by abcman13 » Thu Jul 11, 2013 1:20 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11287 - Pseudoprime numbers

Post by brianfry713 » Fri Jul 12, 2013 1:15 am

Input:

Code: Select all

131877361 55808896
0 0
AC output:

Code: Select all

yes
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 11287 - Pseudoprime Numbers

Post by richatibrewal » Sun Nov 02, 2014 8:20 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11287 - Pseudoprime Numbers

Post by brianfry713 » Wed Nov 05, 2014 11:19 pm

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 112 (11200-11299)”