【SNMOJ74】【YMDragon】number

使用gi读入ll并且Miller-Rabin内ll直接相乘的弱智滚粗啦

听说如果\(n\)不是\(4\)并且有平方因子那么答案一定是\(-1\)。。也就是质因数分解之后某一个质数的次数大于\(1\)那么答案不止\(1\)。

这是个很强的结论,考场上并没有看出来。。似乎稍微贪心一下就能得到这个结论了

首先将\(n\)分解质因数为\(\prod_{i=1}^{k}p_i^{c_i}\)

对于一个数\(nq\)满足\(\sigma_0(nq)=n\),有两种情况:

  1. \(q=\prod_{i=1}^{k}p_i^{d_i}\),\(nq=\prod_{i=1}^{k}p_i^{c_i+d_i}\),其中\(d_i\ge 0\)。表示\(q\)只由\(n\)中出现过的质因子组成。
  2. \(q=p’\prod_{i=1}^{k}p_i^{d_i}\),\(nq=p’\prod_{i=1}^{k}p_i^{c_i+d_i}\),其中\(d_i\ge 0\),\(p’\ne 1\),\((p’,q)=1\)。表示\(q\)中出现了别的质因子。

那么如果是第二种情况,\(p’\)中可以取不同的质数,方案就有无限种,答案为\(-1\)。

我们知道\(\sigma_0\)是个积性函数,那么又有

对于第一种情况,\(\prod_{i=1}^{k}(c_i+d_i+1)=n\)

对于第二种情况,\(c’\prod_{i=1}^{k}(c_i+d_i+1)=n\),其中\(c\)为任意大于\(1\)的正整数

考场上想到这里就gg了,用一些奇怪的贪心判的\(-1\)。那么如何判断第二种情况是否存在呢?

注意到一个奇怪的不等式:\(k\le p^{k-1}\),\(p\)为质数,当且仅当\(k=1\)或\(p=k=2\)时取等号。

那么首先有\(c_i+1\le p^{c_i}\),也就是说只要令每个\(c_i+d_i+1=p^{c_i}\)就是一个合法解。

如果\(n\)有一个大于\(2\)的质因子\(p\)的次数\(k\)大于\(1\)或者有\(2\)的质因子且次数大于\(2\),由刚才的结论,有\(c_i+1\le p^{c_i-1}\)。那么可以将\(c_i+d_i+1=p^{c_i}\)变为\(p(c_i+d_i’+1)=p^{c_i-1}\)。将\(p\)提出,就变成了第二种情况。

如果\(n\)不存在大于\(2\)且次数大于\(1\)的质因子并且质因子\(2\)的次数为\(2\),

  1. 如果存在别的质因数\(p\),令\(c_x\)为\(x\)的次数,那么\(p\ge c_2+1=3\)且\(c_p=1\),\(2(c_2+1)(c_p+1)\le 2^2 p\),就可以提一个\(2\)出来,答案为\(-1\)。
  2. 如果不存在,此时\(n=4\),有唯一解\(8\)。

于是这样就可以判断\(-1\)了。

同时我们发现,因为次数全部为\(1\),那么问题就变得简单了。将\(c_i+d_i+1\)和\(p_i\)一一对应即是所有方案,共\(k!\)个。

由于\(n\le 10^{18}\),那么\(k\)最大只有\(15\)。使用pollard-rho和miller-rabin分解质因数,状压dp即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz