1

我在Codechef March Long Contest的问题GCD 条件中获得 WA 。 请告诉我我做错了什么或代码产生错误答案的一些测试用例。

问题链接

我对每个素数都使用了 RMQ（范围最大查询） 

for(i=0;i<limit;i++)
{
    int sz=b[i].size();
    if(!sz)continue;
    int level=0;
    cc[i].resize(sz);
    for(j=0;j<sz;j++)cc[i][j].push_back(b[i][j]);//level 0
    for(level=1;(1<<level)<=sz;level++)
    {
        for(j=0;j+(1<<level)<=sz;j++)
        {
            int c1=cc[i][j][level-1];
            int c2=cc[i][j+(1<<(level-1))][level-1];
            int mx=(a[c1]<a[c2])?c2:c1;
            cc[i][j].push_back(mx);
        }
    }
}

首先，我已转换为如下结构：-

示例输入：- 10 6 20 15 8

(b[i]-->存储 i 的因子的索引)

b[2]--> 1,2,3,5
b[3]--> 2,4
b [5]--> 1,3,4


现在实现RMQ后，如下：-



(cc[i][j][k] 存储 b[i][j] 和 b[i][j+(2^k)-1] 之间最大元素的索引)

cc[2][0]-- >1,2,3,5
cc[2][1]-->1,3,3
cc[2][2]-->3

cc[3][0]-->2,4
cc[3][1]-->4

cc[5][0]-->1,3,4
cc[5][1]-->3

我的代码

4

1 回答 1

2

100 1
88 33 23 56 97 54 8 74 43 95 91 63 38 13 7 7 52 29 6 85 70 15 52 18 78 9 85 51 28 43 4 68 75 78 75 23 32 34 46 74 28 520 46 74 28 520 23 29 90 45 96 93 14 73 2 99 75 81 93 31 100 19 8 75 93 39 60 41 64 88 30 100 5 84 46 28 89 20 56 30 64 3 22 78 75 35 76 3 8 3 9 2 30 93
95 95 97

输出是-1 -1，但是 gcd(38, 95) = 19，所以 ans 应该是38 1。

在第 75 行将 'break' 替换为 'continue' 给了 AC :)

于 2014-03-18T15:34:29.613 回答