UVa 11426 (欧拉函数 GCD之和) GCD - Extreme (II)

题意:

求sum{gcd(i, j) | 1 ≤ i < j ≤ n}

分析:

有这样一个很有用的结论:gcd(x, n) = i的充要条件是gcd(x/i, n/i) = 1,因此满足条件的x有phi(n/i)个,其中Phi为欧拉函数。

所以枚举i和i的倍数n,累加i * phi(n/i)即可。

 1 #include <cstdio>
 2 typedef long long LL;
 3
 4 const int maxn = 4000000;
 5
 6 int phi[maxn + 10];
 7 LL f[maxn + 10];
 8
 9 void phi_table()
10 {
11     phi[1] = 1;
12     for(int i = 2; i <= maxn; i++) if(!phi[i])
13         for(int j = i; j <= maxn; j += i)
14         {
15             if(!phi[j]) phi[j] = j;
16             phi[j] = phi[j] / i * (i-1);
17         }
18 }
19
20 int main()
21 {
22     phi_table();
23
24     for(int i = 1; i <= maxn; i++)
25         for(int j = i*2; j <= maxn; j += i)
26             f[j] += i * phi[j / i];
27     for(int i = 3; i <= maxn; i++) f[i] += f[i - 1];
28
29     int n;
30     while(scanf("%d", &n) == 1 && n) printf("%lld\n", f[n]);
31
32     return 0;
33 }

代码君

时间: 03-05

UVa 11426 (欧拉函数 GCD之和) GCD - Extreme (II)的相关文章

UVa 11440 (欧拉函数) Help Tomisu

题意: 给出N和M,统计区间x ∈ [2, N!],x满足所有素因子都大于M的x的个数. 分析: 首先将问题转化一下,所有素因子都大于M 等价于 这个数与M!互素 对于k大于M!,k与M!互素等价于 k % M! 与 M!互素 所以我们可以求出φ(M!)(φ为欧拉函数) 然后乘以N! / M!,最后答案再减一(因为是从2开始统计的) 欧拉函数的公式为a phifac[n] = φ(n!),我们递推求phifac 当n为合数时,n!和(n-1)!的素因数的集合是一样的,所以phifac[n] =

UVA - 10820欧拉函数的应用

这是一道很基础的欧拉函数的题目 题意要求  (x,y) 互质 &&x<=n&&y<=n 求互质对数 可以运用容斥,求出 phi(n)=n(1-1/n1)(1-1/n2)......(1-1/nk); 因为(2,4) (4,2) 算两对,所以 答案为 2*f(n)+1; #include<stdio.h> #include<string.h> #include<stdlib.h> #include<iostream>

UVA 11426 - GCD - Extreme (II) 欧拉函数-数学

Given the value of N, you will have to ?nd the value of G. The de?nition of G is given below:G =i<N∑i=1j∑≤Nj=i+1GCD(i, j)Here GCD(i, j) means the greatest common divisor of integer i and integer j.For those who have trouble understanding summation no

uva 11317 - GCD+LCM(欧拉函数+log)

题目链接:uva 11317 - GCD+LCM 题目大意:给定n,求出1~n里面两两的最大公约的积GCD和最小公倍数的积LCM,在10100进制下的位数. 解题思路:在n的情况下,对于最大公约数为i的情况又phi[n/i]次.求LCM就用两两乘积除以GCD即可. #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; ty

hdu2588 gcd 欧拉函数

GCD Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1567    Accepted Submission(s): 751 Problem Description The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes writte

UVA11426 GCD - Extreme (II)---欧拉函数的运用

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=473&problem=2421&mosmsg=Submission+received+with+ID+13800900 Given the value of N, you will have to ?nd the value of G. The de?nition

hdu (欧拉函数+容斥原理) GCD

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1695 看了别人的方法才会做 参考博客http://blog.csdn.net/shiren_Bod/article/details/5787722 题意 a,b,c,d,k五个数,a与c可看做恒为1,求在a到b中选一个数x,c到d中选一个数y,使得gcd(x,y)等于k,求x和y有多少对. 首先可以想到选取的必是k的倍数,假设是x和y倍,则x和y一定是互质的在,那么就变成了求1到b/k和1到d/k的之

hdoj 1787 GCD Again【欧拉函数】

GCD Again Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2673    Accepted Submission(s): 1123 Problem Description Do you have spent some time to think and try to solve those unsolved problem af

hdu 1695 GCD 欧拉函数+容斥

题意:给定a,b,c,d,k x属于[1 , c],y属于[1 , d],求满足gcd(x,y)=k的对数.其中<x,y>和<y,x>算相同. 思路:不妨设c<d,x<=y.问题可以转化为x属于[1,c / k ],y属于[1,d/k ],x和y互质的对数. 那么假如y<=c/k,那么对数就是y从1到c/k欧拉函数的和.如果y>c/k,就只能从[ c/k+1 , d ]枚举,然后利用容斥.详见代码: /****************************