1007 - Mathematically Hard
Time Limit: 2 second(s) | Memory Limit: 64 MB |
Mathematically some problems look hard. But with the help of the computer, some problems can be easily solvable.
In this problem, you will be given two integers a and b. You have to find the summation of the scores of the numbers from a to b (inclusive). The score of a number is defined as the following function.
score (x) = n2, where n is the number of relatively prime numbers with x, which are smaller than x
For example,
For 6, the relatively prime numbers with 6 are 1 and 5. So, score (6) = 22 = 4.
For 8, the relatively prime numbers with 8 are 1, 3, 5 and 7. So, score (8) = 42 = 16.
Now you have to solve this task.
Input
Input starts with an integer T (≤ 105), denoting the number of test cases.
Each case will contain two integers a and b (2 ≤ a ≤ b ≤ 5 * 106).
Output
For each case, print the case number and the summation of all the scores from a to b.
Sample Input |
Output for Sample Input |
3 6 6 8 8 2 20 |
Case 1: 4 Case 2: 16 Case 3: 1237 |
Note
Euler's totient function applied to a positive integer n is defined to be the number of positive integers less than or equal to n that are relatively prime to n. is read "phi of n."
Given the general prime factorization of , one can compute using the formula
思路:就是求欧拉函数,先素数打表,再欧拉函数打表,最后求下前缀和;
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<stdlib.h>
6 #include<queue>
7 using namespace std;
8 bool pr[5*1000006]={0};
9 int prime[5*100006];
10 unsigned long long oula[5*1000006];
11 typedef long long LL;
12 int main(void)
13 {
14 LL i,j,p,q;
15 int s,k;
16 scanf("%d",&k);pr[0]=true;
17 pr[1]=true;
18 for(i=0;i<5*1000006;i++)
19 oula[i]=i;
20 for(i=2;i<10000;i++)
21 {
22 if(!pr[i])
23 {
24 for(j=i;i*j<=5*1000000;j++)
25 {
26 pr[i*j]=true;
27 }
28 }
29 }int cnt=0;
30 for(i=2;i<5*1000005;i++)
31 {
32 if(pr[i]==false)
33 prime[cnt++]=i;
34 }
35 for(i=0;i<cnt;i++)
36 {
37 for(j=1;prime[i]*j<=5*1000000;j++)
38 {
39 oula[prime[i]*j]=oula[prime[i]*j]/prime[i]*(prime[i]-1);
40 }
41 }
42 for(i=2;i<=1000000*5;i++)
43 {
44 oula[i]=oula[i-1]+oula[i]*oula[i];
45 }
46 for(s=1;s<=k;s++)
47 {
48 scanf("%lld %lld",&p,&q);printf("Case %d: ",s);
49 printf("%llu\n",oula[q]-oula[p-1]);
50 }
51 return 0;
52 }
最新文章
- Java集合专题总结(1):HashMap 和 HashTable 源码学习和面试总结
- WEB 用户指南 -- WEB 系统结构文档
- 变通实现微服务的per request以提高IO效率(二)
- [推荐]两款Flash上传插件(1)–CFUpdate文件批量上传组件
- C语言共用体内存计算
- csharp: Flash Player play *.flv file in winform
- chrome浏览器关闭标签页面
- Linux 安装oracle10g 配置dataguard 介绍和步骤
- java的File类的 delete方法删不掉文件的原因分析
- 【剑指offer】Q40:数组中出现一次的数
- 【转】windows 7系统安装与配置Tomcat服务器环境
- Python爬虫框架Scrapy获得定向打击批量招聘信息
- 彩蛋 Python之道
- 如何离线安装Visual Studio 2017
- Vue实例对象的数据选项
- 【HNOI2002】营业额统计
- springMVC参数的传递方式(1.通过@PathVariabl获取路径参数,2.@ModelAttribute获取数据,3.HttpServletRequest取参,4@RequestParam)
- C++版 - Lintcode 77-Longest Common Subsequence最长公共子序列(LCS) - 题解
- Mapreduce的排序(全局排序、分区加排序、Combiner优化)
- oracle导出表的建表语句拼接SQL