2015/07/09

[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就是最大的指数了。

2015/07/06

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

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

2015/07/04

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

[Description]求值


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

2015/06/29

[BZOJ 2301] Problem b【莫比乌斯反演/容斥原理/分块】

[Description] 有n个询问(n50000),每个询问有五个整数a,b,c,d,k,求有多少个数对(x,y)满足axbcyd,gcd(x,y)=k.(ab50000,cd50000,k50000)

[Solution]
我们发现,计算一个数x在某个闭区间[a,b]内的因数数量并不是很方便,可以转化为x在区间[1,b]的因数的数量-x在区间[1,a-1]的因数的数量(因为求[1,Z]比较好求)。

原问题是,对于所有x∈[a,b],y∈[c,d],求所有gcd(x,y)=k的点对的数量。
根据容斥原理,问题转化为,计算:
所有x∈[1,b],y∈[1,d],所有gcd(x,y)=k的点对的数量
-所有x∈[1,a-1],y∈[1,d],所有gcd(x,y)=k的点对的数量
-所有x∈[1,b],y∈[1,c-1],所有gcd(x,y)=k的点对的数量
+所有x∈[1,a-1],y∈[1,c-1],所有gcd(x,y)=k的点对的数量

所以怎么求解任意x∈[1,n],y∈[1,m],所有gcd(x,y)=k的点对的数量呢?