HDU 5212 莫比乌斯反演

Code

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1306 Accepted Submission(s): 540

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

Output

For each case:

Print an integer,denoting what the function returns.

Sample Input

5 1 3 4 2 4

Sample Output

Hint

gcd(x,y) means the greatest common divisor of x and y.

题意：给定序列1≤i,j≤n，求gcd(a[i],a[j])∗(gcd(a[i],a[j])−1)之和。

思路：倍数莫比乌斯反演。

代码：

 1 #include<bits/stdc++.h>
 2 #define  ll long long
 3 using namespace std;
 4 const int N = 1e5 + 5;
 5 const int mod=10007;
 6 int t;
 7 //线性筛法求莫比乌斯函数
 8 bool vis[N + 10];
 9 int pri[N + 10];
10 int mu[N + 10];
11 int sum[N];
12 
13 void mus() {
14     memset(vis, 0, sizeof(vis));
15     mu[1] = 1;
16     int tot = 0;
17     for (int i = 2; i < N; i++) {
18         if (!vis[i]) {
19             pri[tot++] = i;
20             mu[i] = -1;
21         }
22         for (int j = 0; j < tot && i * pri[j] < N; j++) {
23             vis[i * pri[j]] = 1;
24             if (i % pri[j] == 0) {
25                 mu[i * pri[j]] = 0;
26                 break;
27             }
28             else  mu[i * pri[j]] = -mu[i];
29         }
30     }
31     sum[1]=1;
32     for(int i=2;i<N;i++) sum[i]=sum[i-1]+mu[i];
33 }
34 int n,m,k;
35 
36 int a[N];
37 int b[N];
38 int F[N];
39 int main() {
40     mus();
41     while(scanf("%d",&n)==1){
42         int ma=0;
43         memset(F,0, sizeof(F));
44         memset(b,0, sizeof(b));
45         for(int i=0;i<n;i++){
46             scanf("%d",&a[i]);
47             b[a[i]]++;//b[a[i]]的个数
48             ma=max(ma,a[i]);
49         }
50         for(int i=1;i<=ma;i++)
51             for(int j=i;j<=ma;j+=i) F[i]+=b[j];//在范围内i的倍数的个数
52         ll ans=0;
53         for(int i=1;i<=ma;i++){
54             ll res=0;
55             for(int j=i;j<=ma;j+=i){
56                 if(!F[j]) continue;
57                 res+=1ll*mu[j/i]*F[j]*F[j]%mod;//公约数均为i
58             }
59             ans=(ans+res*i%mod*(i-1))%mod;//同时乘上i*i-1
60         }
61         ans%=mod;
62         ans+=mod;
63         ans%=mod;
64         printf("%lld
",ans);
65     }
66     return 0;
67 }