即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

USACO-Section1.4 Arithmetic Progressions

编程语言 qq_34600424 54℃ 0评论

2017-6-7

题目描述

求出满足条件的等差数列的首项和公差

解答

枚举法

代码

/*
ID: 18795871
PROG: ariprog
LANG: C++
*/
#include
#include
#include
using namespace std;

ifstream fin("ariprog.in");
ofstream fout("ariprog.out");

const int N=125000;
bool f[N+1];
struct sl{
   int a,b;
}x[10001];
int m,n,r=0;

int cmp(const void *a,const void *b){
   struct sl *k1=(struct sl *)a;
   struct sl *k2=(struct sl *)b;
   if (k1->b==k2->b) return k1->a-k2->a;
   else return k1->b-k2->b;
}


void init(){
   int i,j;
   for (i=0;i<=m;i++){
       for (j=i;j<=m;j++){
         f[i*i+j*j]=true;
       }
   }
}

void res(){
   int i,j;
   for (i=0;i<=2*m*m;i++){
      if (!f[i]) continue;
      for (j=1;j<=2*m*m/(n-1);j++){
         if (i+j>2*m*m||!f[i+j]) continue;
         if (i+j*2>2*m*m||!f[i+j*2]) continue;
         if (i+j*(n-1)>2*m*m||!f[i+j*(n-1)]) continue;
         int cnt=3;
         while (cntif (!f[i+cnt*j]) break;
            cnt++;
         }
         if (cnt==n){
            x[r].a=i;
            x[r].b=j;
            r++;
         }
      }
   }
}

int main(){
   fin>>n>>m;
   init();
   res();
   if (r==0) fout<<"NONE"<else{
      qsort(x,r,sizeof(x[1]),cmp);
      for (int i=0;i" "<return 0;
}

转载请注明:CodingBlog » USACO-Section1.4 Arithmetic Progressions

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情