XJOI-NOIP模拟赛14总结

跪爽跪爽........
-------------------------------------------------------------------------
 
打打牌
给每个数一个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)即可
-------------------------------------------------------------------------
没了?没了。
算算数呢?不会...
题解呢?看不懂...