洛谷——等差数列

题目描述

一个等差数列是一个能表示成 a,a+b,a+2b,…,a+nb (n∈N)a, a+b, a+2b, \dots ,a+nb\space (n \in \mathbb N)a,a+b,a+2b,…,a+nb (n∈N) 的数列。

在这个问题中 aaa 是一个非负的整数，bbb 是正整数。 写一个程序来找出在双平方数集合：

{x∣x=p2+q2∧p,q∈N∩[0,m]}\{ x | x = p^2 + q^2 \wedge p,q \in \mathbb N \cap [0,m]\} {x∣x=p2+q2∧p,q∈N∩[0,m]}

中长度为 nnn 的等差数列。

输入格式

第一行一个正整数 nnn，表示要找的数列长度。 第二行一个非负整数 mmm，表示 p,qp,qp,q 的上界。

输出格式

如果没有找到数列，输出 NONE。

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

这些行应该以 bbb 为第一关键字，aaa 为第二关键字升序排序。

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

输入输出样例

输入 #1

5 7

输出 #1

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

说明/提示

【数据范围】 对于 1000\0% 的数据，3≤n≤253 \le n \le 253≤n≤25，0≤m≤2500 \le m \le 2500≤m≤250。

如果是运行错误的话试试在判断n个数是不是双循环数之前试试加上这个等差数列的最后一项，会不会超过m*m*2的值，如果超过就不用判断了，这个剪枝可以卡住最后的三组样例。

剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝剪枝

#include<stdio.h> int a[125000]; int b[25000]; int main() { int i,j,k=0,l,m,n,find=0; scanf("%d%d",&n,&m); for(i=0;i<=m*m*2;i++) a[i]=0; for(i=0;i<=m;i++) for(j=0;j<=m;j++) a[i*i+j*j]=1; for(i=0;i<=2*m*m;i++) if (a[i]) b[++k]=i; for(j=1;j<b[k];j++) for(i=1;i<k-1;i++){ if(b[i]+(n-1)*j>b[k]) break; //剪枝剪枝剪枝，重点重点重点 for(l=1;l<n;l++) if(!a[b[i]+l*j]) break; if(l==n){ find=1; printf("%d %d\n",b[i],j); } } if(find==0) printf("NONE\n"); return 0; }