某岛

… : "…アッカリ~ン . .. . " .. .
October 24, 2014

POJ 2154. Color

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11116

Polya 计数。
(置换 $$\rho_i$$ 的循环数为 gcd(i, n))
(gcd(i, n) == d 的置换。。有 phi(n/d) 种。。)

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2884620

— UPD —

阅读了 。。。除数函数的渐近上界?
http://vfleaking.blog.163.com/blog/static/174807634201341913040467/
http://vfleaking.blog.163.com/blog/static/174807634201341913040467/

。。。这玩意还是有点复杂的。。。染指不能。。
姑且让我认为她是 $$O(logn)$$ 的吧、、、、

总之经常有 sqrt(n) 枚举会 TLE。。。
dfs 生成约数才行的情况。。
利用 筛法 的 最小素因子。。。可以一边分解因数一边 dfs。。。这样复杂度严格是约数个数的。。。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2886358

不过 n 再大一些这种方法就不太行了。。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2897593
还是老实分解因数吧 0w0。。。
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2897605

——————————————————————————————————————
http://tieba.baidu.com/p/1890586196
但是质因数分解的复杂度就已经是 sqrt(n) 了???
、、、把素数筛出来以后的质因数分解复杂度是多少?似乎和素数密度有关。。。
http://zh.wikipedia.org/wiki/%E8%B3%AA%E6%95%B8%E5%AE%9A%E7%90%86
。。。。。。。。。、、、

— UPD —
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2949797