The Boss on Mars
Time Limit: 2 Seconds
Memory Limit: 65536 KB
On Mars, there is a huge company called ACM (A huge Company on Mars), and it’s owned by a younger boss.
Due to no moons around Mars, the employees can only get the salaries per-year. There are
n employees in ACM, and it’s time for them to get salaries from their boss. All employees are numbered from 1 to
n. With the unknown reasons, if the employee’s work number is k, he can get
k^4 Mars dollars this year. So the employees working for the ACM are very rich.
Because the number of employees is so large that the boss of ACM must distribute too much money, he wants to fire the people whose work number is co-prime with
n next year. Now the boss wants to know how much he will save after the dismissal.
Input
The first line contains an integer T indicating the number of test cases. (1 ≤
T ≤ 1000) Each test case, there is only one integer n, indicating the number of employees in ACM. (1 ≤
n ≤ 10^8)
Output
For each test case, output an integer indicating the money the boss can save. Because the answer is so large, please module the answer with 1,000,000,007.
Sample Input
2
4
5
Sample Output
82
354
Hint
Case1: sum=1+3*3*3*3=82
Case2: sum=1+2*2*2*2+3*3*3*3+4*4*4*4=354
数论题
观察到与n互质的数的性质
比如12=2*2*3
那么与12不互质的数就有2,3,4,6,8,9,10,12
其实就是2的所有倍数,以及3的所有倍数
所以可以先求一个1到12的所有数的四次方和。这个有公式:
n*(n+1)*(6*n*n*n+9*n*n+n-1)/30(先开始就是抄错了。。)
注意这里30最好求一下逆元大概是2000多万
求的所有的四次方和之后当然要减去那些不互质的数的四次方
也就是说分别剪去了2和3的倍数的四次方,注意这里2和3的公倍数被多减去了,所以要加回来
所以容斥原理也要用
我的代码:
分享到:
相关推荐
包含了zoj700多道题目的源代码,在做题时可以参考
zoj 1255 The Path.md
ZJU/zoj 题库上的部分题源码 本人博客: hi.baidu.com/xiaoxianxi_acm
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
zoj 题库 详细解答 解题代码 acm
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
Putting it on a stage should be a big surprise for the audience so all the preparations must be kept absolutely secret. The ACM director suspects one of his competitors of reading his correspondece. ...
zoj 1610 Count the Colors.md
资源包含了每一题的 解题报告和代码,还附有当时比赛的排名!
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
Problem Arrangement zoj 3777
ZOJ题目答案源码
zoj 2011 Secret Code.md