OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SDOI2008】仪仗队

【题目描述】

作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N*N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。现在,C君希望你告诉他队伍整齐时能看到的学生人数。


【输入】

共一个数N。

【输出】

共一个数,即C君应看到的学生人数。

【输入样例】

4

【输出样例】

9

【数据范围】

对于100%的数据,1≤N≤40000

【题解】

我们先考虑去掉最左列和最下行的情况,得到如下式子:


显然通过线性筛预处理莫比乌斯函数后,是可以线性解决这个问题的。现在加上最左列和最下行,在左下角能在最左列和最下行分别看到一个学生,所以上述问题的答案+2即可。

【代码】

1A真是爽~

http://paste.ubuntu.com/10599500/

评论

© OI技术宅 | Powered by LOFTER