hust2015暑假集训 0715 c a coprime

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82839#problem/C

14年鞍山区域赛的题…

记得是当时全场过得第四多的题…

讲题的时候丽洁姐说“莫比乌斯反演blablabla”

当时完全不懂==

嗯,第一次接触了莫比乌斯反演这个东西。。。好像这个东西在数论中挺重要的。

这道题需要注意的是,求和x的互质的个数的时候,1和任何正整数都是互质的,但是1和1互质这一组是不符合条件的….记得判断下。

求Mobius函数好像有一个筛法求(见贾志鹏线性筛.pdf),然后红书上有一个递推求1~n的mobius函数值的方法(见红书23);

然后被强制转化类型坑了2发WA。。。要开long long ,不写强制转换就会WA。。。还没搞明白为什么。看了别人写的代码上有,加上,结果就过了==

知道了。感谢zj学长。 

 等号右边如果是int,左边是LL,超int了也会越界  
就是说c=a*b  如果a 和b 是int  C是long long  如果a*b超过了Int,就会越界…
需要先把两个int类型转化成long long  写成c=long long (a)*long long (b);
 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz