BZOJ3884 - 上帝与集合的正确用法

BZOJ3884 - Click Here

  

Description

  

Input

  第一行给出一个正整数T。

  接下来T行,每行一个正整数p,代表你需要取模的值。

  对于100%的数据,T<=1000,p<=10^7

  

Output

  T行,每行一个正整数,为答案对p取模后的值。

  

Solutions

  给出题人(PoPoQQQ)跪了。感觉这种无限的题目都要靠减小模数来解决啊?(雾)

  令$p=2^k \times q$,其中$q$为奇数(分解必定唯一)。

  则$2^{2^{2^{2…}}}mod\ p=2^k \times (2^{2^{2^{2…}} - k}\ mod\ q)$。

  由于$q$为奇数,因此$q$与$2^{2^{2^{2…}} - k}$互质。

  所以由欧拉定理得$2^k \times (2^{2^{2^{2…}} - k} \, mod \, q)=2^k \times (2^{(2^{2^{2…}} - k) \, mod \, \phi(q)} \, mod \, q)$。

  减法可以化开,然后又变成了原来的格式。但是模数变小了模数变小了模数变小了!!!

  也就是说,这样子不断的化下去,最后模数会变成1,此时答案是确定的。(任何数mod 1均为0)

  因此这样子不断递归下去就可以得到最终解。

  再考虑一下时间复杂度,因为每次模数至少会除以2,因此最多$log \, q​$次模数就会变成1,再加上预处理出欧拉函数的时间为$O(q)$,所以总时间为$O(q+Tlog\ q)$

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang