## USACO 1.4 Arithmetic Progressions （等差数列）

2018年04月28日 ⁄ 综合 ⁄ 共 1320字 ⁄ 字号 评论关闭

【USACO1.4.3】Arithmetic Progressions 等差数列

Time Limit:50000MS  Memory Limit:65536K
Total Submit:47 Accepted:23
Case Time Limit:5000MS

Description

Input

Output

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```

``` /*
ID:wikioi_2
PROG: ariprog
LANG: C++
*/

# include<cstdio>
# include<iostream>

using namespace std;

# define MAX 125000+4

int a[MAX];

int main(void)
{
int n,m;
freopen("ariprog.in","r",stdin);
freopen("ariprog.out","w",stdout);
cin>>n>>m;
for ( int p = 0;p <= m;p++ )
{
for ( int q = 0;q <= m;q++ )
{
a[q*q+p*p] = 1;
}
}

int flag = 0;
int limit = 2*m*m;
int i,j;
for ( i = 1;i <= limit/(n-1);i++ )
{
for ( j = 0;j+(n-1)*i<= limit;j++ )
{
int cnt = 0;
for ( int temp = j;temp <= limit;temp+=i )
{
if ( a[temp] == 1 )
{
cnt++;
}
else
{
break;
}
if ( cnt==n )
{
break;
}
}
if( cnt==n )
{
flag = 1;
cout<<j<<" "<<i<<endl;
}
}
}

if ( flag==0 )
{
cout<<"NONE"<<endl;
}

return 0;
}
```