2014
11-27

# Jacobi symbol

Consider a prime number p and an integer a !≡ 0 (mod p). Then a is called a quadratic residue mod p if there is an integer x such that x2 ≡ a (mod p), and a quadratic non residue otherwise. Lagrange introduced the following notation, called the Legendre symbol, L (a,p):

For the calculation of these symbol there are the following rules, valid only for distinct odd prime numbers p, q and integers a, b not divisible by p:

The Jacobi symbol, J (a, n) ,is a generalization of the Legendre symbol ,L (a, p).It defines as :
1.  J (a, n) is only defined when n is an odd.
2.  J (0, n) = 0.
3.  If n is a prime number, J (a, n) = L(a, n).
4.  If n is not a prime number, J (a, n) = J (a, p1) *J (a, p2)…* J (a, pm), p1…pm is the prime factor of n.

Two integer a and n, 2 < a< =106，2 < n < =106，n is an odd number.

Two integer a and n, 2 < a< =106，2 < n < =106，n is an odd number.

3 5
3 9
3 13

-1
0
1

#include<stdio.h>
#include<string.h>
#include<math.h>
#define ll __int64
#define maxn 1000010
ll prime[maxn];
bool isprime[maxn];
ll exp(ll a,ll b,ll p)
{
ll res=1;
for(;b;b>>=1)
{
if(b&1)
res=(res*a)%p;
a=(a*a)%p;
}
return res;
}

int cal(int a,int n)
{
if(a%n==0)
return 0;
else
return exp(a,(n-1)/2,n)==1?1:-1;
}
int main()
{
freopen("in.txt","r",stdin);
memset(isprime,true,sizeof(isprime));
for(int i=2;i<maxn;i++)
{
for(int j=2;i*j<maxn;j++)
isprime[i*j]=0;
}
int k=0;
for(int i=2;i<maxn;i++)
{
if(isprime[i])
prime[k++]=i;
}
int a,n;
while(scanf("%d%d",&a,&n)==2)
{
int ans;
if(isprime[n]==0)
{
ans=1;
for(int i=0;n!=1&&i<k;i++)
{
if(n%prime[i]==0)
{
int total=0;
while(n%prime[i]==0)
{
total++;
n/=prime[i];
}
int tmp=cal(a,prime[i]);
if(total%2==0&&tmp==-1)
tmp=1;
ans*=tmp;
}
}
}
else
ans=cal(a,n);
printf("%d\n",ans);
}
return 0;
}


1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？