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

Read more »

这是人生第一次打codeforces啊…前前后后发生了很多事,手一抖又写了篇Blog.

…其实前几天就有所准备,昨天晚上大约7点才发现当晚有比赛qwq,租的房子又没网==,只能凌晨待在学校打啊!!!瞬间大家就就纷纷打电话回家说今晚不回去了==然后有家长打电话给cy问了问情况,然后那个爆炸啊==,cy勒令我们回家,还扬言要到学校来抓人–,然后我们就决定在机房关灯锁门,装作不在==还花了半个小时堵了门。

Read more »

考了三道比较简单的数学题(题目来源网络)

傻牛的约数研究(divisor)

[Description]

傻牛最近在研究约数,它觉得这玩意很牛逼。
首先,对于一个数字 X 来说,设 F(X) 表示 X 的约数个数,可以先将 X 表达成为若干个质数的幂次
之积,即 X=p1k1*p2k2 *……*psks,然后 F(X)=(k1+1)*(k2+1)*……*(ks+1) 。傻牛觉得
这个碉堡了。有一天它想,我们是不是可以求出 F(1)+F(2)+F(3)+……+F(N) 的值呢?结果,它
晕掉了。

Read more »

HNOI2008 明明的烦恼

[Description]

自从明明学了树的结构,就对奇怪的树产生了兴趣…… 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

[Input]

第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Read more »

(题目来自朱全民老师PPT)
题目如下(样例: n=3 m=2)
A 给定N个不同的球,放进M个不同的盒子,盒子允许为空,有多少种方案? 样例输出:8
B 给定N个不同的球,放进M个不同的盒子,盒子不允许为空,有多少种方案? 样例输出:6
C 给定N个不同的球,放进M个相同的盒子,盒子允许为空,有多少种方案? 样例输出:4
D 给定N个不同的球,放进M个相同的盒子,盒子不允许为空,有多少种方案? 样例输出:3
E 给定N个相同的球,放进M个不同的盒子,盒子允许为空,有多少种方案? 样例输出:4
F 给定N个相同的球,放进M个不同的盒子,盒子不允许为空,有多少种方案? 样例输出:2
G 给定N个相同的球,放进M个相同的盒子,盒子允许为空,有多少种方案? 样例输出:2
H 给定N个相同的球,放进M个相同的盒子,盒子不允许为空,有多少种方案? 样例输出:1

Read more »

P.S. 这篇主要是自己记记玩玩的,可能只有我一个人看的懂…

图论就这么浩浩荡荡搞了一个多星期…感觉很一般。
随着专题并没有什么思路,这几天跟着大白皮过了一遍,那就随着这个思路再过一遍知识点,复习一遍经典题。

Read more »