bzoj 1041: [HAOI2008]圆上的整点（一个数能分解成多少个，两个数的平方和）

求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。

思路：

先把 r^2 分解质因数，看看这些质因数有什么。

假设这个质因数的个数是 x

如果这个质因数 是2 就不管他，

如果这个质因数，%4==1 ， ans = ans * (x+1);

如果这个质因数，%4==3，如果 x 是奇数，那么这个数 r^2 就不能分解成两个整数的平方和，

如果 x 是偶数，那么  ans = ans * 1;

 

这个题目，我们可以先分解 r ，

质因数是 2 不管他，

如果 % 4 == 3， 那么 这个质因子在 r^2 下的个数肯定是偶数个，所以也不用管它了。

如果 % 4 == 1 ， 答案累乘。 

 

#include <bits/stdc++.h>
#define mem(x,v) memset(x,v,sizeof(x)) 
#define go(i,a,b)  for (int i = a; i <= b; i++)
#define og(i,a,b)  for (int i = a; i >= b; i--)
#define MID(a,b) (a + b) / 2
#define lson now << 1
#define rson now << 1 | 1
using namespace std;
typedef long long LL;
const double EPS = 1e-10;
const int INF = 0x3f3f3f3f;
const int N = 1e5+10;
int f[N],g[N];
int n,m;
int main(){
	cin>>n;
	if (n == 0){
		cout<<1<<endl;
		return 0;
	}
	m = int(sqrt(n)) + 1;
	int t = 1;
	go(i,2,m){ //分解质因数。分解到 n 的平方根就行了，如果后面还有一个大质数，判断一下。
		if (n %  i == 0){
			int k = 0;
			while(n % i == 0) {
				n /= i; k++;
			}
			g[t] = i;
			f[t++] = k;
		}
	}
	if (n>1) g[t] = n,f[t++] = 1;
	int ans = 1;
	go(i,1,t-1){
		if (g[i] == 2 || g[i] % 4 == 3) continue; //如果这个质数模4余3，或者质数是2，直接跳过。
		ans *= (f[i]*2+1); //否则， 质数的个数 *2+1，与答案相乘。
	}
	ans *= 4; // 我们算出来的答案是一个象限内的，最后 * 4；
	cout<<ans<<endl;
	return 0;
}