当前位置:首页 > 开发 > Web前端 > Ext > 正文

UVA 11426 - GCD - Extreme (II) (数论)

发表于: 2015-11-13   作者:互联网   来源:转载   浏览:
ext
摘要: UVA 11426 - GCD - Extreme (II) 题目链接 题意:给定N。求∑i<=ni=1∑j<nj=1gcd(i,j)的值。 思路:lrj白书上的例题,设f(n) = gcd(1, n) + gcd(2, n) + ... + gcd(n - 1, n).这种话,就能够得到递推式S(n) = f(2) + f(3) + ... + f(n) ==> S

UVA 11426 - GCD - Extreme (II)

题目链接

题意:给定N。求i<=ni=1j<nj=1gcd(i,j)的值。

思路:lrj白书上的例题,设f(n) = gcd(1, n) + gcd(2, n) + ... + gcd(n - 1, n).这种话,就能够得到递推式S(n) = f(2) + f(3) + ... + f(n) ==> S(n) = S(n - 1) + f(n);.
这样问题变成怎样求f(n).设g(n, i),表示满足gcd(x, n) = i的个数,这样f(n) = sum{i * g(n, i)}. 那么问题又转化为怎么求g(n, i),gcd(x, n) = i满足的条件为gcd(x / i, n / i) = 1,因此仅仅要求出欧拉函数phi(n / i),就能够得到与x / i互质的个数,从而求出gcd(x , n) = i的个数,这样总体就能够求解了

代码:

#include <stdio.h>
#include <string.h>

const int N = 4000005;

int n;
long long phi[N], s[N], f[N];

int main() {
	phi[1] = 1;
	for (int i = 2; i < N; i++) {
		if (phi[i]) continue;
  		for (int j = i; j < N; j += i) {
  			if (!phi[j]) phi[j] = j;
  			phi[j] = phi[j] / i * (i - 1);
  		}
 	}
 	for (int i = 1; i < N; i++) {
 		for (int j = i * 2; j < N; j += i) {
 			f[j] += phi[j / i] * i;
		}
  	}
  	s[2] = f[2];
  	for (int i = 3; i < N; i++)
  		s[i] = s[i - 1] + f[i];
	while (~scanf("%d", &n) && n) {
		printf("%lld\n", s[n]);
 	}
	return 0;
}


版权声明:本文博客原创文章,博客,未经同意,不得转载。

UVA 11426 - GCD - Extreme (II) (数论)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号