题目:The Euler function phi is an important kind of function in number theory, phi(n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate phi(a) + phi(a+1) + … + phi(b).

Input
There are several test cases. Each line has two integers a, b (2 < a < b < 3000000). Output Output the result of phi(a) + phi(a+1) + ... + phi(b) Sample Input 3 100 Sample Output 3042 链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=339#problem/K 题意:本题是关于欧拉函数的求和问题,通过两个筛选法,先是将范围内素数求出来,在是将范围内每个数对应欧拉函数求出,以后每次输入数据,只需遍历相加即可。 代码: #include
#include “stdio.h”
#define N 3000001
int c[N],phi[N];
int main()
{
long long int a,b,s;
int i,j;
c[0]=c[1]=1;
for(i=2;i*i

发表评论

电子邮件地址不会被公开。

Post Navigation