http://poj.org/problem?id=2591

设置三个游标p、q和i,p和q初始值均为1,i初始值为2,a[1] = 1。
其中p用于生成2*a[p]+1,q用于生成3*a[q]+1,i用于指向数组a新生成的元素。然后有如下规则:
若2*a[p]+1 < 3*a[q]+1,则a[i++] = 2*a[p]+1,然后p++
若2*a[p]+1 > 3*a[q]+1,则a[i++] = 3*a[q]+1,然后q++
若2*a[p]+1 == 3*a[q]+1,则a[i++] = 2*a[p]+1,然后p++,q++

/*157ms,39340KB*/

int a[10000005] = {0, 1};

int main()
{
    int p = 1, q = 1, i, n;
    Forr(i, 2, 10000001)
    {
        a[i] = min(2 * a[p] + 1, 3 * a[q] + 1);
        if (a[i] == 2 * a[p] + 1) p++;
        if (a[i] == 3 * a[q] + 1) q++;
    }
    while (~SI(n)) PI(a[n]);
    return 0;
}

Comments

comments powered by Disqus