NOIP集训-10.19总结
NOIP集训-10.20总结

XJOI-NOIP模拟赛14总结

YYY posted @ 2015年10月19日 18:47 in OI相关 with tags gcd 位运算 数论 欧拉函数 , 148 阅读
跪爽跪爽........
-------------------------------------------------------------------------
 
给每个数一个level
从高位枚举到低位,如果某一位能被某个当前level最大的数乘以x得到,那么这个数的level就加一
(如果有某个level不是最大的数这一位为1,那么跳过这一位)
这样搞直到level最大的数只有一个或者到了最低位为止
-------------------------------------------------------------------------
首先可以知道gcd(a[i],n)的倍数都能被i跑到
gcd(a[i],n)一定是n的约数,然后枚举n的所有约数
对于n的每个约数d,只需要统计gcd(i,n)刚好为d的i个数,这样就可以做到不重不漏
对于所有gcd(i,n)刚好为d的i,它除以d之后一定是和n/d互质的,这样的数的个数也就是phi(n/d)
因此对于所有d | n且存在gcd(a[i],n) = d,累加phi(n/d)即可
-------------------------------------------------------------------------
没了?没了。
算算数呢?不会...
题解呢?看不懂...
LOL

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter