Mathematically Hard LightOJ-1007(欧拉定理+前缀和)

Description

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

3

6 6

8 8

2 20

Sample Output

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 ø(n)using the formula

在数论中,对正整数n,欧拉函数  是小于或等于n的正整数中与n互质的数的数目,对欧拉函数打表;

注意 :long long 需要用无符号型;

代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long ll;
const int maxx=5001000;
ll a[maxx];
void init()
{
    for(int i=0; i<maxx; i++)
        a[i]=i;
    for(int i=2; i<maxx; i++)
    {
        if(a[i]==i)
        {
            for(int j=i; j<maxx; j+=i)
                a[j]=a[j]/i*(i-1);
        }
    }
    for(int i=2; i<maxx; i++)
        a[i]=a[i]*a[i]+a[i-1];
}
int main()
{
    init();
    int t,Case=0;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        printf("Case %d: ",++Case);
        cout<<a[m]-a[n-1]<<endl;
    }
    return 0;
}

原文地址:https://www.cnblogs.com/dwj-2019/p/11349390.html

时间: 08-13

Mathematically Hard LightOJ-1007(欧拉定理+前缀和)的相关文章

Lightoj 1007 - Mathematically Hard

1007 - Mathematically Hard    PDF (English) Statistics Forum 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 giv

1007 - Mathematically Hard

   PDF (English) Statistics Forum 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. Yo

LightOJ 1269 - Consecutive Sum(字典树)

题目链接:LightOJ 1269 - Consecutive Sum 题目大意:给定一个序列,选定一段区间的亦或和,输出最大和最小. 解题思路:最大很简单,对所有前缀建立字典树,然后尽量往反向走:最小则需要往正向走,并且向正向走的时候要扣 除自己本身. #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 50005 * 32; c

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> typ

LightOJ 1295 Lighting System Design (排序+dp)

题目链接:LightOJ 1295  Lighting System Desig 题意:给出n种灯(v,k,c,l)分别是灯的(电压,所需电源费用,灯的单价,所需灯的数量),电压高的灯可以代替电压低的灯但是电压低的灯不能代替电压高的等,每种灯的电压各种相同,问选n种灯最小的花费. 思路: 因为电压高的灯可以代替电压低的灯--按电压高到低排序, 然后求前缀和--因为当出现代替时可以,快速统计灯的花费. 然后就是dp--状态方程:dp[i] 买前i类灯的最少花费,sum[i]前缀和.dp[i]=mi

LightOJ 1295 Lighting System Design dp

链接:http://lightoj.com/volume_showproblem.php?problem=1295 1295 - Lighting System Design PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 32 MB You are given the task to design a lighting system for a huge conference hall. After do

COGS 696. [IOI1996][USACO 2.3] 最长前缀

★   输入文件:prefix.in   输出文件:prefix.out   简单对比时间限制:1 s   内存限制:128 MB 描述 USACO 2.3.1 IOI96 在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的.生物学家对于把长的序列分解成较短的序列(即元素)很感兴趣. 如果一个集合 P 中的元素可以通过串联(元素可以重复使用,相当于 Pascal 中的 “+” 运算符)组成一个序列 S ,那么我们认为序列 S 可以分解为 P 中的元素.元素不一定要全部出现(如下例中B

【BZOJ-1218】激光炸弹 前缀和 + 枚举

1218: [HNOI2003]激光炸弹 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1778  Solved: 833[Submit][Status][Discuss] Description 一种新型的激光炸弹,可以摧毁一个边长为R的正方形内的所有的目标.现在地图上有n(N<=10000)个目标,用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置,每个目标都有一个价值.激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破

mysql批量删除相同前缀的表格

如果你网站后台没法运行mysql,就进phpmyadmin,然后运行一段代码.假如要删除织梦cms的dede_前缀的表,则运行 Select CONCAT( 'drop table ', table_name, ';' )   FROM information_schema.tables   Where table_name LIKE 'dede_%'; 然后,会得一个查询列表,然后点击选择全部,并复制下来这一大串代码.重新点击你安装的程序所对应的数据库,然后点击上面的sql,运行复制下来的一段

LightOJ 1030 Discovering Gold【概率】

题目链接:http://www.lightoj.com/volume_showproblem.php?problem=1030 题意:基础概率题. 代码: #include <stdio.h> #include <string.h> #include <vector> #include <string> #include <algorithm> #include <iostream> #include <iterator>