博文

目前显示的是 七月, 2015的博文

[UVa 10662] Perfect P-th Powers【质因数分解/欧几里得算法/初等数论】

[Description]

给定一个x(int 范围),求它最多能开多少次方。也就是满足x=y^k的最大k值。
[Solution]

把x质因数分解。令x=p1^k1*p2^k2*…*pn^kn,找到所有k的gcd,所以x=(p1^(k1/gcd)*p2^(k2/gcd)*…*pn^(kn/gcd))^gcd.

可以证明,gcd就是最大的指数了。

[BZOJ 4173]数学【欧拉函数】

图片
[Description]
(1<=n,m<=10^15)

[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】

图片
[Description]求值


[Solution]
不要被无限个2吓到了,这一题有一些有趣的性质可以发掘的。
这里介绍两个解法。

[BZOJ 1951] 古代猪文【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】

图片
[Description] 求

[Solution] 容易得到,


所以,重点在怎么求