P9063 [yLOI2023] 分解只因数 题解

P9063 [yLOI2023] 分解只因数 题解

题意

分解给定的 \(n\) 的质因数，判断是否全为奇数。

思想

因为我不是黑子，所以我根本没考虑“只因”的发音对思路的极大提示。
当我首次看到本题时，立马手写了欧拉筛。

void GetPrime(longint n)
{
	...
}
...
for (reg int i = 1; i <= sqrt(n); ++i)
{
    if (n % Prime[i] == 0 && Prime[i] % 2 == 0)
    {
        flag = false;
        break;
    }
    while (n != 1 && n % Prime[i] == 0)
        n /= Prime[i];
    if (n == 1)
        break;
}
...

筛到 $ 5 \times 10^7 $ 需要 500ms。
然后放心的 Ctrl+S。
然后一看样例——这规模数组存的下？！
当我荔枝地考虑出题人是不是黑子想做什么，同机房的 dalao 交题时大喊一声“ji”时，我好像明白了什么。。。
『只因数』==『奇数』
显然对于一个正整数，它有可能存在的偶数质因数只有 $ 2 $。
如果它存在一个偶数质因数，那它就不是『只因数』。
综上所述：只需要判断 $ n $ 的奇偶性即可。

贴个代码

int main()
{
    reg int T;
    scanf("%d", &T);
    while (T--) 
    {
        scanf("%lld", &n);
        printf(n % 2 ? "Yes\n" : "No\n");
    }
    return 0;
}

未放出全文，珍惜账号请勿 ctj。