1 | # include <bits/stdc++.h> |
—————————————————————————————————————————
给定你一个质数p (p < 10^8),请你确定最小的x^2 + y^2 (其中x, y都是正数),使得x^2 + y^2 = 0 (mod p)
首先根据p为素数,能想到i*i%p的循环节是p.
所以说如果选择数的话 一定在这个循环节里面,
然后能想到$ii+jj=ppp+pp$
然后想到枚举平方数找存不存在$ii+jj=p $ ,复杂度为 1e8差不多能过
然后写出了下列代码,就TLE了
1 | # include <bits/stdc++.h> |
最后贯彻**“遇事不决先打表”**这个思想,发现,如果素数形如4*k+3这种,结果就是 否则就是
1 | # include <bits/stdc++.h> |