POJ 2154. Color

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

Polya 計數。
(置換 的循環數為 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/

。。。這玩意還是有點複雜的。。。染指不能。。
姑且讓我認為她是 的吧、、、、

總之經常有 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