Description

一个等差数列是一个能表示成a, a+b, a+2b,…, a+nb (n=0,1,2,3,…)的数列。 在这个问题中a是一个非负的整数,b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p^2+q^2的数的集合)S中长度为n的等差数列。

Input

第一行: N(3<= N<=25),要找的等差数列的长度。 第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。

Output

如果没有找到数列,输出`NONE’。 如果找到了,输出一行或多行, 每行由二个整数组成:a,b。 这些行应该先按b排序再按a排序。 所求的等差数列将不会多于10,000个。

Sample Input

5
7

Sample Output

1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24

解题思路:枚举。公差 b : 1~(n-1)*d<=2*m*m,首项 a : 0~a+(n-1)*d<=2*m*m,长度从1~n。此枚举保证先按b排序再按a排序,故找到后即可直接输出。

———————-我是华丽丽分割线—————————–

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

bool vis[125005];
int num[32000],len;//251/2*252

void init(int m){
    int i,j;
    len=0;
    memset(vis,false,sizeof(vis));
    for(i=0;i<=m;i++){
        for(j=i;j<=m;j++){
            vis[i*i+j*j]=true;
            num[len++]=i*i+j*j;
        }
    }
    sort(num,num+len);
    //可能有重复a*a+b*b==c*c+d*d(a<b,c<d,a!=c,b!=d) 故需去重
    for(i=j=0;j<len-1;j++){
        if(num[j]==num[j+1])
            continue;
        num[i++]=num[j];
    }
    num[i++]=num[j];
    len=i;
}

void solve(int n,int m){
    int i,j,k,flag=0;
    for(j=1;num[0]+(n-1)*j<=2*m*m;j++){//公差为正整数
        for(i=0;num[i]+(n-1)*j<=2*m*m && i<len;i++){//首项为非负整数
            for(k=1;k<n;k++){//长度
                if(vis[num[i]+k*j]==false)
                    break;
            }
            if(k==n){
                flag=1;
                printf(“%d %d\n”,num[i],j);
            }
        }
    }
    if(!flag)
        printf(“NONE\n”);
}

int main(){
    int n,m;
    while(scanf(“%d%d”,&n,&m)!=EOF){
        init(m);
        solve(n,m);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation