首页 > 代码库 > 【bzoj4804】欧拉心算 欧拉函数
【bzoj4804】欧拉心算 欧拉函数
题目描述
给出一个数字N
输入
第一行为一个正整数T，表示数据组数。
接下来T行为询问，每行包含一个正整数N。
T<=5000,N<=10^7
输出
按读入顺序输出答案。
样例输入
1
10
样例输出
136
题解
欧拉函数
其中用到了
这个推导很简单：由欧拉函数的定义，$\sum\limits_{i=1}^k\sum\limits_{j=1}^i[\gcd(i,j)=1]=\sum\limits_{i=1}^k\varphi(i)$，此时$i\ge j$，而当$i\le j$时情况相同。最后减掉重复计算的(1,1)即为左边。
然后剩下的就好说了，预处理欧拉函数$\varphi$和其前缀和$sum$，分块枚举$\lfloor\frac nd\rfloor$的取值并计算即可。
#include <cstdio>#include <algorithm>using namespace std;#define N 10000010typedef long long ll;const int m = 10000000;int prime[N] , tot , phi[N];ll sum[N];bool np[N];int main(){ int i , j , t , n , last; ll ans; sum[1] = phi[1] = 1; for(i = 2 ; i <= m ; i ++ ) { if(!np[i]) phi[i] = i - 1 , prime[++tot] = i; for(j = 1 ; j <= tot && i * prime[j] <= m ; j ++ ) { np[i * prime[j]] = 1; if(i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } sum[i] = sum[i - 1] + phi[i]; } scanf("%d" , &t); while(t -- ) { scanf("%d" , &n) , ans = 0; for(i = 1 ; i <= n ; i = last + 1) last = n / (n / i) , ans += (sum[last] - sum[i - 1]) * sum[n / i]; printf("%lld\n" , 2 * ans - sum[n]); } return 0;}
【bzoj4804】欧拉心算 欧拉函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。