wordpress原生相册/seo营销排名

Description
给出一奇素数p和一整数a，求勒让德符号
Input
第一行一整数T表示用例组数，每组用例输入两个整数a和p，2 < p < 1e9是奇素数，a满足a!=0(mod p)且|a|<=1e9
Output
对于每组用例，输出的值，每组输出后跟一空行
Sample Input
3
29 79
2 29
1 3
Sample Output
Scenario #1:
-1

Scenario #2:
-1

Scenario #3:
1

Solution
欧拉判别准则
Code

#include<cstdio>
using namespace std;
typedef long long ll;
ll mod_pow(ll a,ll b,ll p)
{a=(a%p+p)%p;ll ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;
}
int main()
{int T,a,p,res=1;scanf("%d",&T);while(T--){scanf("%d%d",&a,&p);printf("Scenario #%d:\n",res++);if(mod_pow(a,(p-1)/2,p)==1)printf("1");else printf("-1");printf("\n\n");}return 0;
}