Code

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 877    Accepted Submission(s): 348
**

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

思路：莫比乌斯反演；

F[x]表示sum(gcd(a,b))(x|gcd(a,b)),那么我们需要求f(x)（gcd(a,b)==x），那么根据莫比乌斯反演可得

f(x) = sum(u(y)F（y/x）)(x|y);然后答案就是sum（f(x)*（x*(x-1)））;所以我们先线性筛出莫比乌斯函数，然后再求每个数

的因数，复杂度（n*log（n））

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 typedef long long LL;
10 using namespace std;
11 bool prime[10005];
12 int ak[10005];
13 LL mul[10005];
14 LL cnt[10005];
15 vectorvec[10005];
16 int mod = 10007;
17 int main(void)
18 {
19 int i,j;
20 int cn = 0;
21 mul[1] = 1;
22 for(i = 2; i <= 10000; i++)
23 {
24 if(!prime[i])
25 {
26 ak[cn++] = i;
27 mul[i] = -1;
28 }
29 for(j = 0; j < cn&&(LL)ak[j]*i<=10000; j++)
30 {
31 if(i%ak[j])
32 {
33 prime[i*ak[j]] = true;
34 mul[i*ak[j]] = -mul[i];
35 }
36 else
37 {
38 prime[i*ak[j]] = true;
39 mul[i*ak[j]] = 0;
40 break;
41 }
42 }
43 }
44 int n;
45 for(i = 1;i <= 10000;i++)
46 {
47 for(j = 1;j <= sqrt(i);j++)
48 {
49 if(i%j==0)
50 {
51 vec[i].push_back(j);
52 if(i/j!=j)
53 vec[i].push_back(i/j);
54 }
55 }
56 }
57 while(scanf("%d",&n)!=EOF)
58 { int maxx = 0;
59 memset(cnt,0,sizeof(cnt));
60 int i,j;
61 for(i = 0; i < n; i++)
62 {scanf("%d",&ak[i]);maxx = max(maxx,ak[i]);}
63 for(i = 0; i < n; i++)
64 {
65 for(j = 0;j < vec[ak[i]].size();j++)
66 { int x = vec[ak[i]][j];
67 cnt[x]++;
68 }
69 }//printf("%lld\n",cnt[1]);
70 LL sum = 0;
71 for(i = 1;i <= maxx;i++)
72 {
73 for(j = i;j <= maxx;j+=i)
74 {
75 sum = sum + mul[j/i]*(cnt[j]*cnt[j])*(i*(i-1)%mod)%mod;
76 sum%=mod;
77 }
78 }
79 printf("%lld\n",(sum%mod+mod)%mod);
80 }
81 return 0;
82 }