[HAOI2008]圆上的整点
神仙题
求满足(x^2+y^2=R^2(x,yinmathbb{Z}))的数对$(x,y)个数
高斯整数:是个复数,形如(a+bi),其中(a,b)均为整数
高斯质数是高斯整数,不能分成高斯整数的乘积
那就是在求模长为(R^2)的高斯整数个数
显然高斯整数模长可以表示成((a+bi)(a-bi)),即一对共轭复数的积
考虑(R^2=(a+bi)(a-bi))的方案数,令(N=R^2)(事实上N不是完全平方数这题也能做)
先将N分解成若干个质数之积
随意假设(N=3^2*5^2)
还要继续分下去,分成若干个高斯质数
然后这里用到一个结论:形如(4n+1)的质数能分成两个高斯质数的乘积,形如(4n+3)的不行(视频里也没有说为啥)
所以上面的n可以分成(3^2*(2+i)(2-i)(2+i)(2-i))
要把这些分成两组,每组都在另一边有它的共轭复数对应
(3^2)只能一边放一个((2+i)^2(2-i)^2)有3种方法(左边放0,1,2个((2+i)))
于是就有3种分法,乘4以后(N=225)的答案就是12
继续看几个例子:
- (N=3^3*5^2)时,两边的3无论如何也不能平衡,答案是0
- (N=3^2*5^3)时,左边可以放0,1,2,3个((2+i)),答案是4(*4=16)
- (N=3^2*5^3*13^4)时,左边可以放0,1,2,3个(2+i)和0,1,2,3,4个(3+2i),答案就是20(×4=80)
可以发现这样的规律:
将N分解质因数
ans=1
for i in 所有质因数
if i形如4n+1:
if i的次数为奇数:
ans=0 # 无法安排这个质因数使得两边是共轭复数
else:pass # 什么也没有发生,这个质因数只有一种放法,就是两边放同样多个
else:ans*= i的次数+1 # i=(a+bi)(a-bi),左边可以放0~次数个(a+bi)
然后就结束了。
吗?
如果有质因数是2咋搞啊。。。
事实上不需要搞这个,因为2可以分成((1+i)(1-i)),只能是一个在左一个在右,然而交换这两个数实际上是一边(*frac{1+i}{1-i}=i)另一边(/frac{1+i}{1-i}=i),实际上和最后的答案×4是一样的操作,所以质因数2对答案并没有影响
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
int main(){
int n=gi();
long long ans=1;
for(int i=2;i*i<=n;++i)
if(n%i==0){
int p=0;while(n%i==0)n/=i,++p;
if(i%4==1)ans*=2*p+1;
}
if(n>1){
if(n%4==1)ans*=3;
}
printf("%lld
",ans*4);
return 0;
}
还有,实际上是不会有0出现的,因为输入的是个整数,平方之后所以质因子次数都是偶数