首页 > 代码库 > NEU 1440 The minimum square sum (平方剩余和欧拉准则)
NEU 1440 The minimum square sum (平方剩余和欧拉准则)
若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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。