传送门
题意是输入两组数 a 和 b,要求判断 A=∏i=1nai 除以 B=∏i=1mbi 是否为质数,如果是则输出 YES
否则输出 NO
。
太蒟蒻了只做出来第一题 QAQ
数据范围中 n 和 m 都可以到达 105 级别,而且单个的数 ai 和 bi 达到了 1012 的数量级,显然不能用朴素的方法做(即使自带高精的 Python 也存不下这么多位数吧)
我们发现输入的都是两个天文数字的因子,显然当一个数拥有除 1 以外的两个及以上的因子时不是质数。还有一个很重要的条件就是对于任意一个数字,保证其在 bi 中出现的次数不多于在 ai 中出现的次数,也就是说,可以约去相同的数字!
怎么办呢?可以考虑拿 STL 自带的 map 构造映射,用来记录每个因子出现的次数,map<long long, int> cnt
,其中 Key
是输入的因子,Value
是这个因子出现的次数(map<Key, Value>
)。输入第一个数 A 的时候,我们在统计时加上因子出现的次数,输入第二个数 B 的时候减去因子出现的个数(相当于约分了),这样 map 记录的应该是最终除法计算的结果的因子。
接下来就好办了。只要 map 的大小大于 1,那么说明它一定存在两个或以上的不同因子,一定不是质数,输出 NO
即可。
然后如果 map 的大小等于 1 的话,就看这个数出现的次数了,如果出现的次数大于 1,那么它一定也不是质数。
最后如果这个数只出现了一次,说明结果就是这个数,只要用 O(N) 的算法判断这个数是否是质数就可以了。
代码: