首页 > ACM题库 > HDU-杭电 > HDU 3589-Jacobi symbol-最小生成树-[解题报告]HOJ
2014
11-27

HDU 3589-Jacobi symbol-最小生成树-[解题报告]HOJ

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):

Pair

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:

Pair

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;
}

参考:http://blog.csdn.net/lentty1452/article/details/8570335


  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 . 谁能解释下?