Massive Algorithms: Arithmetic Progressions

Arithmetic Progressions - USACO 1.4.3

An arithmetic progression is a sequence of the form a, a+b, a+2b, ..., a+nb where n=0,1,2,3,... . For this problem, a is a non-negative integer and b is a positive integer.

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p² + q² (where p and q are non-negative integers).

TIME LIMIT: 5 secs

PROGRAM NAME: ariprog

INPUT FORMAT

Line 1:	N (3 <= N <= 25), the length of progressions for which to search
Line 2:	M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

SAMPLE INPUT (file ariprog.in)

5  7

OUTPUT FORMAT

If no sequence is found, a singe line reading `NONE'. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first.
There will be no more than 10,000 sequences.

SAMPLE OUTPUT (file ariprog.out)

http://mangogao.com/read/83.html

首先直接把所有能表示成p²+q²的数算出来，存入一个表中。然后每次从表里选出两个数，以它们的差作为公差，然后扩展，看能否扩展到指定的位。最后将答案进行排序即可。

首先用bool组表示所有范围内的双平方数，枚举每个数列的起点和公差，搜索层数的话用循环分别加0~N-1个公差进行判断。考虑到数据比较大，当首项加上N-1个公差超过了最大范围时break可以稍微优化一点。

int len, q, total = 0;

bool ok, is_pfs[MAX_NUM] = {0};

struct Prog

{

    int a, b;

} ans[MAX_ANS_NUM];

bool compare(Prog x, Prog y)

{

    if (x.b < y.b || (x.b == y.b && x.a < y.a)) return true;

    return false;

}

void get_pfs()

{

    for (int i = 0; i <= q; ++i)

        for (int j = i; j <= q; ++j)

            is_pfs[i * i + j * j] = true;

    // for (int i = 0; i < 2*q*q; ++i)

    // {

    //  if (is_pfs[i]) cout <<"[Debug] pfs: "<<i<<endl;

    // }

}

void solve()

{

    int i, j=0;

    for (i = 0; i <= 2 * q * q; ++i)

{

        //find the b

        for (j = 1; j <= 2 * q * q; ++j)

{

            //stop properly

            if ((i + j * (len - 1)) > 2 * q * q) break;

            // suppose it's good

            ok = true;

            // check this prog

            for (int k = 0; k < len; ++k)

                if (!is_pfs[i + j * k])

{

                    ok = false;

                    break;

}

            if (ok)

{

                ans[total++].a = i;

                ans[total - 1].b = j;

                 // cout <<"[Debug] a = "<<i<<" b = " << j <<" "<< total<<endl;

}

}

}

}

int main()

{

    ifstream fin("ariprog.in");

    fin >> len >> q;

    fin.close();

    //get all the pfs

    get_pfs();

    //find the first number of a prog

    solve();

    //sort the answer

    sort(ans, ans + total, compare);

    ofstream fout("ariprog.out");

    if (total == 0)

        fout << "NONE" << endl;

    else

        for (int i = 0; i < total; ++i)

            fout << ans[i].a << " " << ans[i].b << endl;

    fout.close();

    return 0;

}

看了题解发现漏考虑了一个很重要的优化，枚举首项的时候应该直接枚举双平方数，这就要求将双平方数另存一个a[]，当然是有序的。其次对于公差，也应该是直接枚举a[]中两个数的差更好。另外两个优化，一个最有效的是我想到的，另一个细节是判断一个数列时从后往前判断。
http://jackneus.com/programming-archives/arithmetic-progressions/

struct prog{

    int base;

    int increm;

    bool operator < (const prog & b) const{

        return increm < b.increm;

}

};

int N;

vector<prog> progs;

bool valid(vector<bool>& S, int base, int step){

    for(int i = 1; i < N; i++){

        if(!S[base + step * i]) return false;

}

    return true;

}

int main(){

    ifstream in("ariprog.in");

    ofstream out("ariprog.out");

    int M;

    in >> N >> M;

    vector<bool> S(M * M * 2);

    for(int i = 0; i < S.size(); i++) S[i] = false;

    for(int p = 0; p <= M; p++){

        for(int q = 0; q <= M; q++){

            S[p * p + q * q] = true;

}

}

    for(int i = 0; i < S.size(); i++){

        if(S[i]){

            for(int j = 1; j < (S.size() - i) / N + 2 * N; j++){

                if(valid(S, i, j)){

                    prog solut;

                    solut.base = i;

                    solut.increm = j;

                    progs.push_back(solut);

}

}

}

}

    if(progs.size() != 0){

        sort(progs.begin(), progs.begin() + progs.size());

        for(int i = 0; i < progs.size(); i++){

            out << progs[i].base << " " << progs[i].increm << endl;

}

}

    else out << "NONE" << endl;

}

http://leonlu.iteye.com/blog/1125404
首先决定在算术级数中找双平方还是在双平方中找算术级数。直觉是在双平方数中找算术级数，首先生成所有的双平方数，保存在一个boolean数组中，这个数组大小为250×250×2=125000。然后外层循环取a（从1开始在双平方数中取），内层循环取b（从1开始取到(125000-a)/(N-1)，因为满足a+(N-1)*b <=125000），得到a，b后要验证是否能构成长度为n的算术级数，若能则储存结果。最后按b，a升序的顺数输出a，b。


	public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new FileReader("ariprog.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
	"ariprog.out")),true);

	// read data
	int N = Integer.parseInt(in.readLine());
	int M = Integer.parseInt(in.readLine());
	// max: 250 * 250 * 2 = 125000
	int MM2 = MM2;

	// generate bisquares into a boolean array
	// loop times: 251 * 252 /2 = 31626
	boolean[] bisquares = new boolean[MM2+1];
	for(int p = 0; p <= M; p++)
	for(int q = p; q<= M; q++)
	bisquares[pp + qq] = true;

	// search and pruning
	List<int[]> res = new ArrayList<int[]>();
	for(int a = 0; a < MM2; a++){
	if(!bisquares[a]) continue;
	label:
	for(int b = 1; b <= (MM2-a)/ (N-1); b++){ // a+ (N-1) * b <= MM2
	for(int i = 1; i<= N-1; i++){
	if(!bisquares[a + b * i])
	continue label;
	}
	res.add(new int[]{a,b});
	}
	}

	// sort and print
	Collections.sort(res,new Comparator<int[]>(){
	public int compare(int[] o1, int[] o2) {
	if(o1[1] < o2[1]) return -1;
	if(o1[1] > o2[1]) return 1;
	if(o1[0] < o2[0]) return -1;
	if(o1[0] < o2[0]) return 1;
	return 0;
	}});
	if(res.size() == 0) out.println("NONE");
	for(int[] ab : res)
	out.println(ab[0]+ " " + ab[1]);

	System.exit(0);
	}

http://jusaco.blogspot.com/2013/07/arithmetic-progressions-solution.html
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new FileReader("ariprog.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(
"ariprog.out")),true);

int N = Integer.parseInt(in.readLine());
int M = Integer.parseInt(in.readLine());
// max: 250 * 250 * 2 = 125000
int MM2 = M*M*2;

boolean[] bisquares = new boolean[MM2+1];
for(int p = 0; p <= M; p++)
for(int q = p; q<= M; q++)
bisquares[p*p + q*q] = true;

List<int[]> res = new ArrayList<int[]>();
for(int a = 0; a < MM2; a++){
if(!bisquares[a]) continue;
label:
for(int b = 1; b <= (MM2-a)/ (N-1); b++){
for(int i = 1; i<= N-1; i++){
if(!bisquares[a + b * i])
continue label;
}
res.add(new int[]{a,b});
}
}

Collections.sort(res,new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
if(o1[1] < o2[1]) return -1;
if(o1[1] > o2[1]) return 1;
if(o1[0] < o2[0]) return -1;
if(o1[0] < o2[0]) return 1;
return 0;
}});
if(res.size() == 0) out.println("NONE");
for(int[] ab : res)
out.println(ab[0]+ " " + ab[1]);

System.exit(0);
}
}

https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter1/ariprog.java
Read full article from arithmeticprogressions - codetrick