本文主要是介绍XTU-OJ 1355-Euler‘s Totient Function，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
对于整数n，定义ϕ(n)为小于或等于n，并与n互质的整数的个数，比如6,比它小的和它互质的数有1,5,所以ϕ(6)=2。 如果n=pk11⋅pk22⋅…⋅pkmm，其中pi为不相同的素数。 那么ϕ(n)=n⋅(1−1p1)⋅…⋅(1−1pm)。
我们定义f(a,b)=∑bi=aϕ(i),请你写一个程序求f(a,b)。
输入
第一行是一个整数T(1≤T≤10000)，表示样例的个数。 每个样例是一行，为两个整数a,b(1≤a≤b≤3000000)。
输出
每行输出一个样例的结果。
样例输入
3 1 6 1 100 1 1000000样例输出
12 3044 303963552392
解题思路： 欧拉筛进阶---->欧拉函数 + 前缀和 (老熟人了)
本题是一个很纯粹的模板题，就是计算 欧拉函数 公式（后面离散数学也会提到，话又说回来了，认真学习）。具体的概念解析有个博主写的很好，可以直接学习，点我跳转。
AC代码：
#include <stdio.h>int T,a,b;
const int MAXN = 3e6+5;
bool vis[MAXN]; // 筛选MAXN个素数
int prime[MAXN]; // 把素数依次存放在该数组中
__int64 phi[MAXN] = {0,1};void oula()
{for (int i = 2; i < MAXN; i ++){if ( !vis[i]){prime[++prime[0]] = i; // prime[0] --> 筛选出的素数个数phi[i] = i-1; // 素数i的 ϕ(i) = i-1;}for (int j = 1; j <= prime[0] && i <= MAXN/prime[j]; j ++){vis[i*prime[j]] = 1; // 素数prime[j]的i倍为 合数phi[i*prime[j]] = phi[i]*phi[prime[j]];if (i % prime[j] == 0){phi[i*prime[j]] = phi[i]*prime[j];break;}}}for (int i = 1; i <= 3e6; i ++)phi[i] += phi[i-1];
}int main()
{oula();scanf("%d",&T);while ( T --){scanf("%d %d",&a,&b);printf("%I64d\n",phi[b]-phi[a-1]);}return 0;
}这篇关于XTU-OJ 1355-Euler‘s Totient Function的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
