专栏首页Code思维奇妙屋Uva_11462 GCD - Extreme (II)

Uva_11462 GCD - Extreme (II)

题目链接

题意:

  给定一个n, 求:GCD(1, 2) + GCD(1, 3) + GCD(2, 3) + …… + GCD(1, n) + GCD(2, n) + …… + GCD(n-1, n);

     设f(n) = ΣGCD(i, n), i = 1, 2, 3, ... , n-1

  本题即求:f(2) + f(3) + f(4) + ... + f(n)

  设s(n) = f(2) + f(3) + f(4) + ... + f(n)

  1)

  令 d = GCD(x, n), d 是 x, n的约数

  所以, 1 = GCD(x/d, n/d)  所有满足条件的 x/d 的个数 则为 n/d的 欧拉函数值phi(n/d);

  即满足d = GCD(x, n) 的x的个数为phi(n/d) , 这部分的和为phi(n/d) * d;

  得, f(n) = Σ (i * phi(n/i)) i = [1, n-1]区间内n的所有约数。

  2)

  得出f(n) 的值, 我们就可以递推出s(n)的值了, s(n) = s(n-1) + f(n) , n >= 3

  代码如下:

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 using namespace std;
16 #define LL long long
17 #define MAXN 4000010
18 #define MOD 1000000007
19 #define eps 1e-6
20 int n;
21 LL f[MAXN], s[MAXN];
22 int phi[MAXN];
23 int euler_phi(int n)
24 {
25     int m = (int)sqrt(n + 0.5);
26     int ans = n;
27     for(int i = 2; i <= m; i ++)
28     if(n % i == 0)
29     {
30         ans = ans / i * (i - 1);
31         while(n % i == 0) n /= i;
32     }
33     if(n > 1) ans = ans / n * (n - 1);
34     return ans;
35 }
36 
37 void phi_table(int n)
38 {
39     for(int i = 0; i <= n; i ++) phi[i] = 0;
40     phi[1] = 1;
41     for(int i = 2; i <= n; i ++)
42     if(!phi[i])
43     {
44         for(int j = i; j <= n; j += i)
45         {
46             if(!phi[j]) phi[j] = j;
47             phi[j] = phi[j] / i * (i - 1);
48         }
49     }
50 }
51 void init()
52 {
53     for(int i = 1; i < MAXN; i ++)
54         for(int j = 2 * i; j < MAXN; j += i)
55             f[j] += i * phi[j/i];
56     s[2] = f[2];
57     for(int i = 3; i < MAXN; i ++)
58         s[i] = s[i-1] + f[i];
59 }
60 
61 int main()
62 {
63     phi_table(MAXN - 5);
64     init();
65     while(scanf("%d", &n) && n)
66     {
67         printf("%lld\n", s[n]);
68     }
69     return 0;
70 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Uva_11762 Race to 1

      给一个数n, 每次从小于等于n的素数里选一个P, 如果能被n整除, 那么就n就变成n / P。 

    若羽
  • LightOJ_1038 Race to 1 Again

      给一个数n, 每次操作是随机的选择一个[1,N]区间内能够被n整除的数进行除法, 然后得到一个新的n。

    若羽
  • LightOj_1027 A Dangerous Maze

      你在一个迷宫里, 开始的时候你面前有n个门, 选择每个门的概率相等, 有两种结果:

    若羽
  • 树状数组—(离散化)求比较大的数逆序数的个数

    柴银磊
  • size_t类型

    青木
  • 关于Java的反射机制,你需要理解这些..

    反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意一个方法和属性;这种动态获取的信息以及动态调用对象...

    方志朋
  • Flutter 更新&升级

    https://flutter-io.cn/posts/announcing-flutter-1-7-9.html

    林小帅
  • 创建和使用Windows静态链接库

    首先明确这篇文章的目的,我希望大家能够通过这篇文章了解一下如何在实际工作中创建和使用Windows平台下的静态链接库。关于链接库的概念,希望大家参考维基百科”L...

    用户1221057
  • 【Bazinga HDU - 5510 】【考察strstr()的使用】【贪心】

    1.题目大致说的是让你输出符合这种条件(在所给的字符串中至少有一个不是它的子串)的字符串对应的label,若没有输出-1; 2.判断子串可以用string.h...

    _DIY
  • Java面经:去哪儿四轮面试真题分享

    废话不多说,前几天参加去哪网面试,面经如下: 去哪网java实习生面总共分为四轮(我也不知道为什么这么多)。 一面(技术面) 1.自我介绍,并分析简历上的项目,...

    牛客网

扫码关注云+社区

领取腾讯云代金券