UVA11426 GCD - Extreme (II) —

题目链接：https://vjudge.net/problem/UVA-11426

题意：

求 ∑ gcd(i，j)，其中 1<=i<j<=n 。

题解：
1. 欧拉函数的定义：满足 0<x<n 且 gcd(x,n) = 1 的x有euler[n]个。

2. 可以推论出：满足 0<2*x<2*n 且 gcd(2*x,2*n) = 2 的2*x同样有euler[n]个，推向一般：满足 0<k*x<k*n 且 gcd(k*x,k*n) = k 的k*x有euler[n]个。解释：其实就是对于n来说，在1~n-1内与它互质的数都乘上相应的倍数，同时n也乘上相应的倍数，因而他们的最大公约数也为乘上的倍数，但不管如何，个数没有改变，仍为euler[n]个，只不过是他们的值“放大”了罢。

3. 有了上述结论，就可以枚举每个欧拉函数euler[n]和系数k，然后进行统计。

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = +;

 int euler[MAXN];

 void getEuler()

 {

     memset(euler, , sizeof(euler));

     euler[] = ;

     for(int i = ; i<MAXN; i++) if(!euler[i]) {

         for(int j = i; j<MAXN; j += i)

         {

             if(!euler[j]) euler[j] = j;

             euler[j] = euler[j]/i*(i-);

         }

     }

 }

 LL sum[MAXN];

 void init()

 {

     getEuler();

     memset(sum, , sizeof(sum));

     for(int i = ; i<MAXN; i++)   // 枚举“单位”欧拉数

         for(int k = ; i*k<MAXN; k++)   // 枚举倍数

             sum[i*k] += k*euler[i];

     for(int i = ; i<MAXN; i++)

         sum[i] += sum[i-];

 }

 int main()

 {

     init();

     int n;

     while(scanf("%d", &n) &&n)

         printf("%lld\n", sum[n]);

 }

巴特西

UVA11426 GCD - Extreme (II) —— 欧拉函数

最新文章

热门文章