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,,
一周排行
  • 如果系统某个端口6379綁定监听ip127.0.0.1,则该端口只会通过来自这个ip的连接请求,拒绝非监听ip主机的连接. telnet 10.10.86.211 9000 Trying 10.10.86.211..
  • 解決pdm打開只顯示表名不顯示字段的步驟
    解决pdm打开只显示表名不显示字段的方法 选中PDM 依次点击 工具-->显示参数选 ...
  • 


    		    7月第2周網路安全報告:境內被植入後門網站2459個
    IDC评述网(idcps.com)07月21日报道:根据CNCERT抽样监测结果和国家信息
  • 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1997   Problem Description n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生
  • 


    		    lvsdr+heartbeat+ldirector
    这里使用vmware虚拟机来实现lvs-dr模型,利用heartbeat来实现lvs-dr
  • 题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1231算法参考:http:[email protected]/blog/static/17154
  • 现在安卓手机实体键是越来越少了,但还是有的,恰好自己就碰上了:按键的事件...百度了一些博客,内容都基本上是完全一样的,虽然可以捕获到事件,但却会和正常的单击冲突.幸好最近开个VPN,google,耶~正确答案马上呈
  • 参考http://www.cnblogs.com/cdtarena/p/3184313.html 这里以C#作为服务端  其实不论C#是服务端还是客户端都不是主要问题 毕竟不论客户端还是服务端 都包括了发送和接收两个 ...
  • 由程序逻辑可以看到 这是一个 客户端和服务端一对一聊天的程序  首先由服务端说第一句话然后对话才开始  且只能客户端一行话  服务端再一行话 这样往复进行  客户端若想不等服务端回应继续说话是不行的 服务端 pack
  • 4台路由器.R1,R2,R3,R4,一字相连. 让R1接口IP ping 通R4接口IP 不准NAT,不准桥接,不准写静态路由,仅仅是接口配IP,还有就是改数据链路层的格式. 呵呵,也许方法不只一种,答出来的那个人.