求和

发表于 分类于 ， 阅读次数： 本文字数： 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*\Phi(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*\Phi(N)/2$
时间复杂度$O(\sqrt {N})$
详见代码1

第二种方法(容斥)

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

$N = p1^{r1}*p2^{r2}*p3^{r3}*…*pn^{rn}$

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

$M = p1*p2*…*pm$

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

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

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

$\sum_{K=1}^{\frac{N}{M}}M*K = M*\frac{(\frac{N}{M}+1)*\frac{N}{M}}{2}$

最后的时间复杂度即$O(\sqrt {N}+2^n)$,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互质的数的和