The Euler function(歐拉函數)

The Euler function

Time Limit : 2/1ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 39   Accepted Submission(s) : 19

Font: Times New Roman Verdana Georgia

Font Size: ← →

Problem Description

The Euler function phi is an important kind of function in number theory, (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 (a)+ (a+1)+....+ (b)

Input

There are several test cases. Each line has two integers a, b (2<a<b<3).

Output

Output the result of (a)+ (a+1)+....+ (b)

Sample Input

3 100

Sample Output

3042
题解:打表水过;
代码:
 1 #include<stdio.h>
 2 #include<string.h>
 3 const int MAXN= 3010;
 4 __int64 dp[MAXN];
 5 int main(){
 6     memset(dp,0,sizeof(dp));
 7     dp[1]=1;
 8     for(int i=2;i<MAXN;i++){
 9         if(dp[i])continue;
10         for(int j=i;j<MAXN;j+=i){
11             if(!dp[j])dp[j]=j;
12             dp[j]=dp[j]/i*(i-1);
13         }
14     }
15     for(int i=2;i<MAXN;i++)dp[i]+=dp[i-1];
16     int a,b;
17     while(~scanf("%d%d",&a,&b))printf("%I64d\n",dp[b]-dp[a-1]);
18         return 0;
19 } 

 

更多相关文章
  • The Euler function Time Limit: 2/1 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submis
  • POJ2689 HDU2824 篩法、歐拉函數
    [email protected]. Prime Distance Time Limit: 1MS Me
  • 找新朋友 Time Limit: 2/1 MS(Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s):6928    Accepted Submission(s): 3593 Problem Des
  • http://poj.org/problem?id=2478 http://acm.hdu.edu.cn/showproblem.php?pid=2824 欧拉函数模板裸题,有两种方法求出所有的欧拉函数,一是筛法,而是白书上的筛法. 首先看欧拉函数的性质: 欧拉函数是求小于n且和n互质(包括1)的正
  • Reflect(歐拉函數)
    Reflect Time Limit: 2/1 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 288    Accepted Submission(s): 174 Problem D ...
  • 此题中对时间有要求,如直接使用欧拉函数求解,每输入一个n,就得进行循环求出<n的每个数的欧拉函数, 这样会超时, 于是我们可预先将欧拉函数打表, 再进行一个循环加法运算,便可不超时得解. #include<iostr
  • 找新朋友 Time Limit: 2/1 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9361    Accepted Submission(s): 4955 Problem De
  • poj3696       快速冪的優化+歐拉函數+gcd的優化+互質
    这题满满的黑科技orz 题意:给出L,要求求出最小的全部由8组成的数(eg: 8,88,,
一周排行
  • 1024x768 Normal 0 false false false EN-US ZH-CN X-NONE MicrosoftInternetExplorer4 /* Style Definitions */ ta
  • Linux 170个常见问题的详细解答 一. 如何建立多用户 提醒大家一句,别一直使用root用户,因为root用户在系统中有着至高无上的权力,一不小心就可能破坏系统.比如我们想删除/temp目录下的文件却将命令不小 ...
  • 周末处理的一次故障,这里简单记录下. 故障现象: 6点1 分左右开始, Hadoop集群异常,所有的hdfs操作都出现问题. 几十个 job报以下错 FAILED: RuntimeException org.apac
  • Java設計模式原型模式(Prototype)
      原型模式属于对象的创建模式.通过给出一个原型对象来指明所有创建的对象的类型,然后用这个
  • css设置opacity 之前看了别人写了一段关于opacity的css代码,没深入理解就copy过来自己用了一段时间,现在重新拿出来又深入研究了一下. .cla{ /* IE 8 */ -ms-filter: &q ...
  • 前言 第一天传送门: 2014 Hangjs 见闻流水账第一天 写作风格跟第一天还是一样的. Slide 每个slide我都会根据自己的理解重新命名一次,用于表达自己的第一看法,主观意见,不喜可吐槽,但是不要喷,就算 ...
  • AngularJS是由Google创建的一种JS框架,使用它可以扩展应用程序中的HTML功能,从而在web应用程序中使用HTML声明动态内容.在该团队工作的软件工程师Brian Ford近日撰写了一篇blog,分享了
  • (轉)MapReduce Design Patterns(chapter 3 (part 1))(五)
    Chapter 3. Filtering Patterns 本章的模式有一个共同点:不会改 ...
  • resetlogs 打开数据库时新生成日志位置问题 若系统中缺少联机日志,以resetlogs方式重建控制文件,那么当我们以alter database open resetlogs方式打开数据库时,新生成的联机日志 ...
  • 


    		    IE無法浏覽網頁,而QQ可以上解決方案
    当只有IE无法浏览网页,而QQ可以上时,则往往由于winsock.dll.wsock32.