题目链接
题意：交代一下勒让德符号与二次剩余，然后告诉你J(a,n)与L的关系，给定a，n，求J(a,n)。
二次剩余的原理我并没有搞太懂= =，想着毕竟不常见，会用板子就好了。在知道如何求勒让德符号的情况下，只需要将n分解质因数，假设n=p1^k1 * p2^k2 * ... *pm^km，则答案为J(a,p1)^k1 * J(a,p2)^k2 * ... * J(a,pm)^km = L(a,p1)^k1 * L(a,p2)^k2 * ... * L(a,pm)^km。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define p_b push_back
#define N 1005
int quick_mod(int a,int b,int c) { int ans = 1; while (b) { if (b&1)ans=(ans*1ll*a)%c; b/= 2; a=(a*1ll*a)%c;} return ans; }
bool notprime[N];
int prime[200],cnt;
void init(){notprime[1]=1;For(i,2,N-1){if(!notprime[i]){prime[cnt++]=i;}for(int j=0;j<cnt&&i*prime[j]<N;j++){notprime[i*prime[j]]=1;if(i%prime[j]==0){break;}}}
}
vector<int> fac;
int Legender(int a,int p)//求勒让德符号
{int ans=(quick_mod(a, (p - 1) / 2, p)%p+p)%p;if(ans==p-1) return -1;else return ans;
}
int solve(int n,int p){fac.clear();int x=p;for(int i=0;i<cnt&&prime[i]<=x;i++){while(x%prime[i]==0) x/=prime[i],fac.p_b(prime[i]);}if(x>1)fac.p_b(x);int tmp=1;for(int i=0;i<(int)fac.size();i++){tmp*=Legender(n,fac[i]);}return tmp;
}
int main()
{init();int n,p;while (scanf("%d%d",&n,&p)!=EOF){printf("%d\n",solve(n,p));}
}