游客 注册 | 登录
中文 | En

2509 - 等差数列

通过次数

0

提交次数

0

时间限制 : 5 秒 内存限制 : 128 MB

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

题目输入

输入包含多组测试数据

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

题目输出

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

输入/输出样例

输入格式

5
7

输出格式

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

C++解答

#include <bits/stdc++.h>
const int maxs=250*250+10;
using namespace std;
struct Ans
{
       int a,d;
       bool operator <(const Ans&b)const
       {
            if (b.d==d) return a<b.a;
            return d<b.d;
       }
};
int S[maxs],n,m,point=0,ans_point=0;
bool vis[maxs*2];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
    Ans ans[10005*3];
    point=0,ans_point=0;
    int i,j,k;
    memset(S,0,sizeof(S));
    memset(vis,0,sizeof(vis));
    for (i=0;i<=m;i++)
    for (j=0;j<=m;j++)
    if (vis[i*i+j*j]==0)
    {
         S[point++]=i*i+j*j;
         vis[i*i+j*j]=1;
    }
    sort(S,S+point);
    for (i=0;i<point;i++)
    for (j=i+1;j<point;j++)
    {
        if (S[i]+(S[j]-S[i])*(n-1)>S[point-1]) continue;
        int last=S[j],d=S[j]-S[i],cnt=2;
        while (vis[last+d] && last+d<=S[point-1] && cnt<n) {cnt++;last=last+d;}
        if (cnt==n)
        {
            ans[ans_point].a=S[i];
            ans[ans_point++].d=d;
        }
    }
    sort(ans,ans+ans_point);
    if (ans_point==0) printf("NONE\n");
    else
    {
         for (i=0;i<ans_point;i++)
         printf("%d %d\n",ans[i].a,ans[i].d);
    }
    }
    return 0;
}
请先登陆