XJOI-NOIP模拟赛14总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
跪爽跪爽........
-------------------------------------------------------------------------
打打牌：
给每个数一个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)即可
-------------------------------------------------------------------------
没了？没了。
算算数呢？不会...
题解呢？看不懂...
评论 (0)
