问题描述:
求一个整数的高斯素因子。
解题思路:
高斯整数
a + bi是素数当且仅当:
1)a、b中有一个是零,另一个数的绝对值是形如
4n + 3的素数;
2)a、b均不为零,而
a2 + b2为素数;
于是只要将每个分解素因子,对于每个素因子P,如果该素因子形如4n+3,则必定能分解成(a+bj)(a-bj) = a^2 + b^2,枚举解决。
代码如下:
#include <iostream>
#include <cmath>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int f[65537], p[65537], size;
int pri[1000], top;
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct point
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int a;
int b;
char oper;
}s[10000];
int num;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//筛选素数
void init()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
f[1] = 1;
int i, j;
for(i = 2; i <= 65536; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(!f[i])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
p[ size++ ] = i;
for(j = i+i; j <= 65536; j += i)
f[j] = 1;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//素因子分解
void Flip(int key)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
top = 0;
for(i = 0; i < size; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(key % p[i] == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
pri[ top++ ] = p[i];
key /= p[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(key % p[i] == 0)
{
pri[ top++ ] = p[i];
key /= p[i];
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(key - 1)
pri[ top++ ] = key;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//高斯素数分解
void Part(int prime)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
if(prime == 2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
s[ num ].a = 1; s[ num ].b = 1; s[ num++ ].oper = '+';
s[ num ].a = 1; s[ num ].b = 1; s[ num++ ].oper = '-';
}else if( (prime - 1) % 4 == 0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(i = 1; ;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int u = int(sqrt(prime - i*i*1.0) + 1e-5);
if(u*u + i*i == prime)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
s[ num ].a = i; s[ num ].b = u; s[ num++ ].oper = '+';
s[ num ].a = i; s[ num ].b = u; s[ num++ ].oper = '-';
break;
}
}
}else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
s[ num ].a = prime; s[ num++ ].b = 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp(const void *a, const void *b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
point *c = (point *)a;
point *d = (point *)b;
if(c->a != d->a)
return c->a - d->a;
if(c->b != d->b)
return c->b - d->b;
return c->oper == '-' ? 1 : -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Print(int key)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
printf("%d", s[key].a );
if(s[key].b == 0)
return;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(s[key].b == 1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("%cj", s[key].oper);
}else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("%c%dj", s[key].oper, s[key].b);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
init();
int i, cas = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(scanf("%d", &n) != EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num = 0;
Flip(n);
for(i = 0; i < top; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Part(pri[i]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort(s, num, sizeof(point), cmp);
printf("Case #%d: ", cas++);
Print(0);
for(i = 1; i < num; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(s[i].a == s[i-1].a
&& s[i].b == s[i-1].b
&& s[i].oper == s[i-1].oper)
continue;
if(i)
printf(", ");
Print(i);
}
puts("");
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)