1.4.3 Arithmetic Progressions 等差数列

code

6 年前

时间： 5ms 内存：64M

描述：

一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。

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

输入：

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

输出：

如果没有找到数列,输出`NONE'。

如果找到了，输出一行或多行, 每行由二个整数组成:a,b。

这些行应该先按b排序再按a排序。

所求的等差数列将不会多于10,000个。

示例输入：

5
7

示例输出：

提示：

参考答案（内存最优[1408]）：

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool a[250*250+5];
int l=0;
struct Node
{
    int a,b;
}node[10001];
int cmp(Node node1,Node node2)
{
    if(node1.b<node2.b)return 1;
    if(node1.b==node2.b&&node1.a<node2.a)return 1;
    return 0;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=m*m*2;i++)
            a[i]=0;
    for(int i=0;i<=m;i++)
        for(int j=0;j<=m;j++)
        {
            a[i*i+j*j]=1;
        }
    int num=0,flg=1;
    for(int i=0;i<=m*m*2&&flg;i++)
    {
        int count=0;
        if(a[i])
        {
            for(int j=1;j<=(m*m*2)/(n-1)&&flg;j++)
            {
                if(i+(n-1)*j>m*m*2)continue;
                for(int k=0;k<n;k++)
                {
                    if(i+j*k>m*m*2)break;
                    if(a[i+j*k])count++;
                }
                if(count==n)
                {
                        node[num].a=i;
                        node[num].b=j;
                        num++;
                        if(num>=10000)flg=0;
                }
                count=0;
            }
        }
    }
    sort(node,node+num,cmp);
    for(int i=0;i<num;i++)
    cout<<node[i].a<<" "<<node[i].b<<endl;
    if(num==0)cout<<"NONE"<<endl;
    return 0;
}

参考答案（时间最优[520]）：

/*
	ID:ayludon3
	LANG:C++
	PROG:ariprog
*/
#include <fstream>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int seq[25000];
bool flag[150000];
struct series
{
    int a;
    int b;
}res[25000];

int cmp(series a,series b )
{
    if(a.b!=b.b)
        return a.b<b.b;
    return a.a<b.a;
}

int main()
{
//    ifstream fin("ariprog.in");
//	ofstream fout("ariprog.out");
    int m,n,i,j,cnt,k,d,temp;
    cin>>n>>m;
//    fin>>n>>m;
    cnt=0;
    memset(flag,0,sizeof(flag));
    for(i=0;i<=m;++i)
        for(j=0;j<=m;++j)
        {
            if(!flag[i*i+j*j])      //去掉重复的双平方数
            {
                seq[cnt++]=i*i+j*j;  //保存所有的双平方数
                flag[i*i+j*j]=1;
            }
        }
    sort(seq,seq+cnt);
    k=0;
    for(i=0;i<cnt;++i)
        for(j=i+1;j<cnt;++j)
        {
            d=seq[j]-seq[i];
            temp=2;        //temp为第n+1项
            if(seq[i]+d*(n-1)>seq[cnt-1])
                break;          //剪枝，判断不存在第n个数满足当前等差，跳出内循环
            while(flag[seq[i]+temp*d])//判断当等差数列项存在，则数列项加1
            {
                temp++;
                if(temp==n)
                    break;
            }
            if(temp==n)   //若等差数列长度为n，记录当前a，b
            {
                res[k].a=seq[i];
                res[k++].b=d;
            }
        }
    if(k==0)
//    fout<<"NONE"<<endl;
     cout<<"NONE"<<endl;
    else
    {
        sort(res,res+k,cmp);
        for(i=0;i<k;i++)
        {
//            fout<<res[i].a<<' '<<res[i].b;
//            fout<<endl;
           cout<<res[i].a<<' '<<res[i].b;
           cout<<endl;
        }
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。