博文

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

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

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

图片
[Description]求值


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

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

图片
[Description] 求

[Solution] 容易得到,


所以,重点在怎么求

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

图片
[Description] 有n个询问(n≤50000),每个询问有五个整数a,b,c,d,k,求有多少个数对(x,y)满足a≤x≤b,c≤y≤d,且gcd(x,y)=k.(a≤b≤50000,c≤d≤50000,k≤50000)

[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的点对的数量呢?

[Codeforces Round #310 (Div. 2)] #ABC题解

没想到时隔两天竟然又打了cf,做了3题就弃疗了。

题目链接:Codeforces Round #310 (Div. 2)

[BZOJ 2440] 完全平方数【莫比乌斯函数/容斥原理/二分法】

图片
[Description] 求第k个无平方因子数。无平方因子数指分解之后所有质因数的次数都为1的数。
[Solution] 
我们可以进行二分操作,查找区间[1,x]里有几个无平方因子数,逐渐缩小范围依次求解。 
然而怎么计算区间[1,x]内无平方因子数的个数Q呢?