usaco_ariprog.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROG: ariprog
LANG: C++
*/ 

#include <fstream>
#include <cstdlib>

using namespace std;

class ResultGroup {
public:
        int a, b;
};

int compare(const void* aa, const void* bb) {
        ResultGroup *a = (ResultGroup*)aa;
        ResultGroup *b = (ResultGroup*)bb;
        if (a->b < b->b) {
                return -1;
        } else if (a->b > b->b) {
                return 1;
        } else if (a->a < b->a) {
                return -1;
        } else if (a->a > b->a) {
                return 1;
        } else {
                return 0;
        }
}
        
int main() {
        int n, m, a, b, loopAMax, loopBMax, maxBisquare, loopIMax;
        bool hasBisquare[125001];
        bool isOK = true;
        ResultGroup results[10000];
        int resultsGot = 0;
        memset(hasBisquare, false, sizeof(bool));
        
        ifstream fin("ariprog.in");
        ofstream fout("ariprog.out");
        
        fin >> n;
        n--;
        fin >> m;
        
        for (int p = 0; p <= m; p++)
                for (int q = 0; q <= m; q++) {
                        hasBisquare[p * p + q * q] = true;
                }
        
        maxBisquare = m * m * 2;
        loopAMax = maxBisquare - n;
        for (a = 0; a <= loopAMax; a++) {
                loopBMax = (maxBisquare - a) / n;
                for (b = 1; b <= loopBMax; b++) {
                        loopIMax = n * b + a;
                        for (int i = a; i <= loopIMax; i += b) {
                                if (!hasBisquare[i]) {
                                        isOK = false;
                                        break;
                                }
                        }
                        if (isOK) {
                                results[resultsGot].a = a;
                                results[resultsGot].b = b;
                                resultsGot++;
                        } else {
                                isOK = true;
                        }
                }
        }
        
        if (resultsGot == 0) {
                fout << "NONE" << endl;
                return 0;
        }
        qsort(results, resultsGot, sizeof(ResultGroup), compare);
        for (int i = 0; i < resultsGot; i++) {
                fout << (results[i].a) << " " << (results[i].b) << endl;
        }
        
        return 0;
}