若p=2或p=4*k+1 则p可以表成两平方数的和的形式 (欧拉和费马已证明,并且有求的方法) 所以答案是p
若p=4*k+3 设a^2=n(mod p) (n!=0) 可以证明不存在b,b^2=p-n(mod p) 即若n是p的平方剩余 则p-n不是p的平方剩余
证明:因为a^2=n(mod p) 所以由欧拉准则 得n^((p-1)/2)=1(mod p)
若b^2=-n(mod p) 那么(-n)^((p-1)/2)=1(mod p)
左边把符号提出来 得(-1)^((p-1)/2)*n^((p-1)/2)
因为p是4*k+3型的 所以(p-1)/2是奇数 所以左边不可能等于1 假设与事实矛盾所以
因此a^2=0(mod p) b^2=0(mod p) 所以答案是2*p*p
#include<bits/stdc++.h> using namespace std; int main() { long long p; while(scanf("%lld",&p)==1) { if(p==2||p%4==1) printf("%lld\n",p); else printf("%lld\n",p*p*2); } return 0; }
NEU 1440 The minimum square sum (平方剩余和欧拉准则),布布扣,bubuko.com
NEU 1440 The minimum square sum (平方剩余和欧拉准则)
原文:http://blog.csdn.net/nenuxlp/article/details/38381187