首页 > 代码库 > LightOj1007 - Mathematically Hard（欧拉函数）
LightOj1007 - Mathematically Hard（欧拉函数）
题目链接：http://lightoj.com/volume_showproblem.php?problem=1007
题意：给你两个数a和b，求他们之间所有数的欧拉值得平方和; a and b (2 ≤ a ≤ b ≤ 5 * 106).
线性打表求值即可;
结果会爆long long，要用unsigned long long %llu形式;
#include <stdio.h>#include <string.h>#include <algorithm>typedef unsigned long long LL;#define N 5000001using namespace std;int f[N] = {0};LL ans[N] = {0};void Init(){ for(int i=2; i<N; i++) { if(f[i]) continue; for(int j=i; j<N; j+=i) { if(!f[j]) f[j] = j; f[j] = f[j]/i*(i-1); } } ans[0] = 0; for(int i=1; i<N; i++) ans[i] = ans[i-1] + (LL)f[i]*f[i];}int main(){ Init(); int T, a, b, t = 1; scanf("%d", &T); while(T--) { scanf("%d %d", &a, &b); printf("Case %d: %llu\n", t++, ans[b]-ans[a-1]); } return 0;}
LightOj1007 - Mathematically Hard（欧拉函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。