Code

Problem Description
WLD likes playing with codes.One day he is writing a function.Howerver,his computer breaks down because the function is too powerful.He is very sad.Can you help him?

The function:

int calc
{

int res=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

{

  res+=gcd(a[i],a[j])*(gcd(a[i],a[j])-1);

  res%=10007;

}

return res;

}

Input
There are Multiple Cases.(At MOST 10)

For each case:

The first line contains an integer N(1≤N≤10000).

The next line contains N integers a1,a2,...,aN(1≤ai≤10000).

Output
For each case:

Print an integer,denoting what the function returns.

Sample Input
5
1 3 4 2 4
Sample Output
64

http://www.2cto.com/kf/201504/395068.html

题目中的函数有很多重复运算，比如gcd(2,3), gcd(3,2)
可以优化为

  for(int i=1; i<=n; i++)
    for(int j=i; j<=n; j++)

不过时间复杂度依然是O(N^2)，估计还是超时，貌似要用到一些数学定理。。。