The Boss on Mars (ZOJ Problem Set - 3547)

ZOJ Online Judge

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3547

問題

会社にはn人いて、i番目の人には給料がi^4だけ支払われている。nと互いに素な番号の人をクビにしたら給料はいくら削減できる？
1<=n<=10^8

解法

n^4の総和はググって調べる(On Siteでも頑張って考えれば作れそう)。クビにした後に支払う金額を考えるとnの素因数を約数に持つ番号の人を列挙すれば良い。これは包除原理を用いると重複なく総和を取ることができる。