Description
给定 \(r\), 求满足 \(x^2+y^2=r^2\) 的整数解组数.
Solution
先丢一个 \(3Blue1Brown\) 的科普向视频: 隐藏在素数规律中的 \(\pi\) https://www.bilibili.com/video/av12131743/
视频的前 \(20\) 分钟就足以解决这道题了, 但还是建议看完.
视频中并没有证明费马平方和定理, 由于证明过程复杂, 就看这里吧.
于是代码就很简单了这篇博客好像毫无价值
- Code
- #include<bits/stdc++.h>
- using namespace std;
- int main()
- {
- int R, ans=1;
- scanf("%d", &R); if (!R) {puts("1"); return 0;}
- for (int i=3, cnt=0; i*i<=R; i+=2, cnt=0)
- {
- while (!(R%i)) cnt++, R/=i;
- if ((i&3)==1) ans*=(cnt<<1|1);
- }
- while (!(R&1)) R>>=1;
- if (R^1 && (R&3)==1) ans*=3;
- printf("%d\n", ans<<2);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3030628.html