题目:
查看原题点击这里-->传送门
题目大意就是随意输入两个数 a,b;输出a到b之间的每个数的欧拉函数之和;
思路:
题目中最大的数是3000000,我们可以先把1~3000000对应的每个数的欧拉函数求解出来。
然后再用一个前缀和数组求出1~3000000对应的欧拉函数之和。
但问题的关键是怎么求出每个数对应的欧拉函数。我们可以用线性筛法。
由欧拉函数公式 phi[n]=n*(1-1/p1)*(1-1/p2)*(1-1/p3)....
我们先找出来一个质数p,然后对于它的的每一个倍数的数组乘(1-1/p)。
结合下面的代码就很容易理解了。
代码:
正确的AC代码,用普通的线性筛。
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; #define ll long long ll sum[3000005]; void work(int n) { //为了节省空间,刚开始sum数组表示每个数对应的欧拉函数 sum[1] = 1; //1的欧拉函数是1; for (int i = 2; i <= n; i++) { if (!sum[i]) { //如果sum[i]还没有背赋值过,就表明i是一个质数 for (int j = i; j <= n; j+=i) { //phi[x]=x*(1-1/p1)*(1-1/p2)*(1-1/p3).... if (!sum[j])sum[j] = j; //相当于给phi[x]赋初值x sum[j] = sum[j] / i * (i - 1); //乘上(1-1/p) } } } for (int i = 2; i <= n; i++) { //这里的sum变成了前缀和 sum[i] += sum[i - 1]; } } int main() { int a, b; work(3000000); while (~scanf("%d%d", &a, &b)) { printf("%lld\n", sum[b] - sum[a - 1]); } return 0; }
很高级但不能通过的代码,伤心。
其实还有一种用欧拉筛求欧拉函数。他能比普通的线性筛更快,但是他需要更多的内存。
这一题需要开3个3000000大的数组,然后就爆空间了,别问我怎么知道的。。。。。。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<vector> using namespace std; #define ll long long int prime[3000010]; int primes[3000010]; int primenum = 0; ll sum[3000010]; void makeprime(int n) { prime[0] = prime[1] = 1; sum[1] = 1; for (int i = 2; i <= n; i++) { if (!prime[i]) { primes[primenum++] = i; sum[i] = i - 1; } for (int j = 0; i * primes[j] <= n; j++) { prime[i * primes[j]] = 1; if (i % primes[j] == 0) { sum[i * primes[j]] = primes[j] * sum[i]; break; } sum[i * primes[j]] = (primes[j] - 1) * sum[i]; } } for (int i = 2; i <= n; i++) { sum[i] += sum[i - 1]; } } int main() { int a, b; makeprime(3000000); while (~scanf("%d%d", &a, &b)) { printf("%lld\n", sum[b] - sum[a - 1]); } return 0; }
番外篇(线性筛真是个好东西)
用来筛质数:
这个就不提了,因为平时也不用,可以用更高效的代码替代。
用来求约数和(包括本身):
void work(int n) { for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j+=i)p[j] += i; } }
用来求约数和(不包括本身):
void work(int n) { for (int i = 1; i <= n/2; i++) { for (int j = i*2; j <= n; j+=i)p[j] += i; } }
用来求欧拉函数:
就如上所示了。哈哈,偷个懒。