ZOJ 3903 Ant（数学，推公示+乘法逆元）

Ant

Time Limit: 1 Second Memory Limit: 32768 KB

There is an ant named Alice. Alice likes going hiking very much. Today, she wants to climb a cuboid. The length of cuboid's longest edge is n, and the other edges are all positive integers. Alice's starting point is a vertex of this cuboid, and she wants to arrive at the opposite vertex. The opposite vertex means the vertex which has no common planes or edges with the starting point. Just like the picture below:

Alice is very clever, she always walks on the shortest path. But she can only walk on the surface of the cuboid. Now, Alice only knows the length of cuboid's longest edge is n, and doesn't know the length of other edges. Suppose the L is the length of shortest path of a cuboid. Alice wants to compute the sum of L² for every possible cuboid.

Input

The first line of input contains an integer T(T ≤ 100) . T is the number of the cases. In the following T lines, there are a positive integer n(1≤n≤10¹⁴) in each line. n is the longest edge of the cuboid.

Output

For each test case, output the sum of L² for every possible cuboid in a line. L is the length of shortest path of a cuboid. It may be very large, so you must output the answer modulo 1000000007.

Sample Input

2
3
4

Sample Output

160
440

Hint

(3,2,1) and (3,1,2) are regrad as the same cuboids.

来自 <http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3903>

【题意】：

已知一长方体的最大边长 N

求所有可能情况下，两对顶角沿表面的最短距离（展开成平面即可）的平方和。

【解题思路】：

若长方体边长为 N A B，则 L^2 = N^2 + (A+B)^2；

即找出所有小于N的A B组合，求出平方和

例如N=3；则有组合

（1，1）（1，2）（1，3）

（2，2）（2，3）

（3，3）

即最终答案中共有 N(N+1)/2 个 N^2；

再考虑 (A+B)^2 的和：

A取值1~N，对于每个A，B取值为x~n；

将 (A+B)^2展开为 A^2+B^2+2AB 求和

其中平方项每个出现 n+1 次,

而2AB项通过代数可得

将上述项依次求和即可，由于取模原因，除法要先求逆元，这里拓展欧几里得易求。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define LL long long
 7 #define mod 1000000007
 8 #define IN freopen("in.txt","r",stdin);
 9 using namespace std;
10 
11 LL x,y,gcd;
12 void ex_gcd(LL a,LL b)
13 {
14     if(!b) {x=1;y=0;gcd=a;}
15     else {ex_gcd(b,a%b);LL temp=x;x=y;y=temp-a/b*y;}
16 }
17 
18 int main(int argc, char const *argv[])
19 {
20     //IN;
21 
22     LL two,six;
23     ex_gcd(2, mod);
24     while(x<0) {x+=mod;y-=2;}
25     two = x;
26     ex_gcd(6, mod);
27     while(x<0) {x+=mod;y-=6;}
28     six = x;
29 
30     int t;scanf("%d",&t);
31     while(t--)
32     {
33         LL n, ans = 0;
34         scanf("%lld",&n);n%=mod;
35 
36         ans = (((((n*n)%mod)*((n*(n+1))%mod))%mod)*two)%mod;
37         ans = (ans + ((((((((n+2)*n)%mod)*(n+1))%mod)*((2*n)%mod+1))%mod)*six)%mod)%mod;
38         ans = (ans + ((((n*n)%mod+n)%mod)*(((((n+1)*n)%mod)*two)%mod))%mod)%mod;
39         LL tmp = (((n*(n+1))%mod)*two)%mod;
40         ans = ((ans - ((tmp*tmp)%mod))%mod+mod)%mod;
41 
42         printf("%lld
", ans%mod);
43     }
44 
45     return 0;
46 }