随笔-141  评论-9  文章-3  trackbacks-0
USACO 1.4.3 Arithmetic Progressions


/*
ID: lorelei3
TASK: ariprog
LANG: C++
*/

#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

const int N = 300000;

bool    flag[N]; 
bool    none_find =true;
int        array[N];

int main(){
    int i,j,num,n,m, def;

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

    in>>n>>m;

    num=0;
    for(i=0;i<=m;++i)
        for(j=0;j<=m;++j){
            if(!flag[i*i+j*j]){
                array[num++] = i*i+j*j;
            }
            flag[i*i+j*j] = true;
        }

    sort(array, array+num);

    //a+(n-1)*b <= m*m+m*m
    bool is;
    int p,c;
    int max = 2*m*m;
    int def_max = max/(n-1);

    for(def=1; def<=def_max; def++){
        for(p=0; array[p]<=(max-((n-1)*def)); p++){
            is = true;
            for(c=(n-1); c>=0; c--){
                if(!flag[array[p]+c*def]){
                    is =false;
                    break;
                }
            }
            if(is){
                none_find = false;
                out<<array[p]<<" "<<def<<endl;
            }
        }
    }

    if(none_find)
        out<<"NONE"<<endl;

    return 0;
}
posted on 2010-11-09 12:54 小阮 阅读(118) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮