算法应该是比较单纯的,先把所有的双平方数找出来,并排序;然后再比如双平方数num[i], num[i + 1],那么a = num[i], b = num[i + 1] – num[i] (num已经排序了),然后便利他们就是,唯一要注意的就是一个大的剪支,当a + (n – 1) b > 最大的双平方数时,那么就结束循环,把所有的答案a, b排序一次输出即可。
LANG: C
ID: yylogoo2
PROG: ariprog
/
#include <stdio.h>
#include <stdlib.h>
int bits[125001];
int num[125001];
int len;
struct box{
int x, y;
}ans[10000];
int end;
void add(int a, int b)
{
ans[end].x = a;
ans[end].y = b;
end++;
}
int com(const void a, const void b)
{
return (int )a – (int )b;
}
int com1(const void a, const void b)
{
struct box i = (struct box)a, j = (struct box)b;
if(i.y != j.y){
return i.y – j.y;
}
return i.x – j.x;
}
int main(void)
{
int i, j, k;
int a, b;
int n, m;
freopen("ariprog.in", "r", stdin);
freopen("ariprog.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i = 0; i <= m; i++){
/
Mistack 2:
下面是从0开始, 我以为从1开始会把零包涵进去..
/
for(j = 0; j <= m; j++){
/
Mistack 1:
这个地方代码弄错了,题目没审清楚,是i^2+j^2而不是ij
/
a = i i + j j;
if(!bits[a]){
num[len++] = a;
bits[a] = 1;
}
}
}
qsort(num, len, sizeof(int), com);
for(i = 0; i < len; i++){
a = num[i];
for(j = i + 1; j < len; j++){
b = num[j] – num[i];
if(a + (n – 1) b > num[len – 1]){
break;
}
for(k = 1; k < n; k++){
if(!bits[a + k b]){
break;
}
}
if(k == n){
add(a, b);
}
}
}
qsort(ans, end, sizeof(struct box), com1);
for(i = 0; i < end; i++){
printf("%d %d\n", ans[i].x, ans[i].y);
}
/
Mistack 3:
忘记如果没有答案时应该输出NONE了
*/
if(end == 0){
printf("NONE\n");
}
return 0;
}