求和

发表于 分类于 ， 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

Description

若两个数的最大公约数为 1，则这两个数互质。现在给出一个正整数 N（1<=2^31-1)，你的任务是求出 1~N 中与 N 互质的数的总和。
Input

一个整数 N

Output

一个整数 sum，表示 1~N 中与 N 互质的数的总和。

Sample Input

1
10

Sample Output

1
20

Analysis

这道题有两种解题方法

第一种方法（数论）
结论:ans=N∗Φ(N)/2

证明:
if gcd(n,i)=1 then gcd(n,n-i)=1 (1<=i<=n)

反证法：

    如果存在K!=1使gcd(n,n-i)=k,那么(n-i)%k==0

    而n%k=0

    那么必须保证i%k=0

    k是n的因子,如果i%k=0那么 gcd(n,i)=k,矛盾出现;

    于是问题变的非常简单： ANS=N*phi(N)/2

    i,n-i总是成对出现，并且和是n

	于是可能就有人问了，如果存在n-i=i那不是重复计算？

    答案是不会

    因为:

            n=2*i->i=n/2

  1. 如果 n 是奇数，那么 n!=2*i, 自然也不存在 n-i=i 和重复计算之说

  2. 如果 n 是偶数，n=2*i 成立，gcd (n,n/2) 必然为 n 的一个因子，这个因子为 1 当且仅当 n==2

  3. 于是对于 n>2 的偶数，绝对不存在 gcd (n,n/2)=1 所以更别说什么重复计算了 

1
2
3
对于n==2

ans=2*1/2=1，正好也满足

所以得到最终公式：ans=N∗Φ(N)/2
时间复杂度 O(N)
详见代码 1

第二种方法 (容斥)

我们可以先求 1..N 中与 N 不互质的数的和。即 GCD(N,x)≠1

N=p1r1∗p2r2∗p3r3∗…∗pnrn

时间复杂度 O(N)
我们尝试构造一个非法的数 M，使得 M|N，由 N 的若干个质因数相乘得到。

M=p1∗p2∗…∗pm

枚举 M 的时间复杂度 O(2n)
对于奇数个质数相乘累加，对于偶数个质数相称累减。
这样得到一个不合法的最小数 M, 我们可以设

Q=M∗K,(1<=k<=N/M)

得到一些列不合法的数 Q, 将他们累加起来，即

∑K=1NMM∗K=M∗(NM+1)∗NM2

最后的时间复杂度即 O(N+2n),n 很小最大只有 10。

详见代码 2
***
Code

代码 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long LL;
LL ans;
int n;

LL phi(int n)
{
	LL ret = n;
	for (int i=2;i<=sqrt(n);i ++)
	{
		if (n%i==0)
		{
			ret = ret/i*(i-1);
			while (n%i==0) n /= i;
		}
	}
	if (n>1) ret = ret/n*(n-1);
	return ret;
}

int main()
{
	//freopen("1164.in","r",stdin);
	//freopen("1164.out","w",stdout);

	while (scanf("%d",&n)!=EOF)
	{
		LL ans;
		if (n==1) ans = 1; else ans = phi(n)*n/2;
		printf("%lld\n",ans);
	}
	return 0;
}

代码 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long LL;
int pri[100];
LL ans,n;

void prepar(int n)
{
	for (int i=2;i<=sqrt(n);i ++)
	{
		if (n%i==0)
		{
			pri[++ pri[0]] = i;
			while (n%i==0) n /= i;
		}
	}
	if (n>1) pri[++ pri[0]] = n;
}

int main()
{
	//freopen("data.in","r",stdin);
	//freopen("1164.out","w",stdout);

	while (scanf("%lld",&n)!=EOF)
	{
		ans = 0;
		prepar(n);
		for (int st=1;st<(1<<pri[0]);st ++) 
		{
			int tot = 0,tmp = 1;
			for (int i=0;i<pri[0];i ++)
				if (st & (1<<i)) tmp *= pri[i+1],tot ++;
			if (tot&1)
				ans += (1+n/tmp)*(n/tmp)/2*tmp;
			else	ans -= (1+n/tmp)*(n/tmp)/2*tmp;
		} 
		ans = (unsigned long long)n*(n+1)/2-ans;
		printf("%lld\n",ans);
	}
	return 0;
}

References

hdu3501 给出一个 N，求 1..N 中与 N 互质的数的和