虽然不能改，但数据实在太水了

我采用了质因数的思路解题，以下是分解质因数部分的代码：

CPP

m1_ = m1; //创建m1的副本
for (int i = 2; i <= ceil(sqrt(m1)); ++i)
    if (m1_ % i == 0 && is_prime(i))
    {
        pf[i] = 0;
        while (m1_ % i == 0)
            m1_ /= i, pf[i]++;
#ifdef local
        printf("get %d^%d,left %d\n", i, pf[i], m1_);
#endif      
    }

代码中的 pf[] 是一个 map<int, int> 对象，pf[i] = j 表示

m1

包含

j

个质因数

i

，即

m1 \mid i^j \land \lnot(m1 \mid i^{j+1})

（意即

m1

整除

i^j

，但不整除

i^{j+1}

）。

但是，对于 for 中的循环变量

i

，我给定的上界是

i\le\lceil\sqrt{m1}\rceil

，会忽略大于之的质因数。这是质数判断中常用的优化，用在质因数分解中显然是不对的。只需构造这样一个数据，就能轻松干掉我的程序：

CPP

1
10 1
2

计算可知，这个数据对应的答案是 -1，因为

10

中有因数

5

，而

2

中没有。但是，因为

5>\lceil\sqrt{10}\rceil=4

，我的代码就会忽略

5

，只记下

2

，这导致它输出了 1。

然而——

这样的代码竟然

AC

了！

似乎显然地，本题数据中的

m1

都是一些小质数的高次幂之积（它甚至想到了

m1=1

的数据都没想到这种数据，令人~~忍俊不禁~~十分疑惑）。

虽然不能改，但数据实在太水了

讨论操作

回复

相关推荐

虽然不能改，但数据实在太水了