The Euler function

﹏ヽ暗。殇╰゛Y 2022-03-18 02:50 135阅读 0赞

题目描述：

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<3000000).

Output

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

Sample Input

3 100

Sample Output

3042

思路：就是求一个区间内的欧拉函数之和，

给出一个结论：

设E( x)为X的欧拉函数，p为质数

对于E（x\*p）

if   p是x的因数  E(x\*p)=E(x)\*p;

else  E (x\*P)=E(x)\*(p-1);

代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxv=3e6+10;
    int v[3000005],a[3000006],b[3000005];//b数组就是欧拉函数
    void init(){
    	for(int i=2;i<3000006;i++){
    		if(!v[i]){
    			a[++a[0]]=i;
    			b[i]=i-1; 
    		}
    		for(int j=1;j<=a[0]&&i*a[j]<3000006;j++){
    			v[i*a[j]]=1;
    			if(i%a[j]==0){
    				b[i*a[j]]=b[i]*a[j];
    				break;
    			}else{
    				b[i*a[j]]=b[i]*(a[j]-1);
    			}
    		}
    	}
    } 
    int main(){
    	int n,m,len;
    	init();
    	long long sum=0;
    	cin>>n>>m;
    	if(n>m)swap(n,m);
    	for(int i=n;i<=m;i++)sum+=b[i];
    	cout<<sum;
    	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关 FUNCTION leader.sum does not exist. Check the ‘Function Name Parsing and Resolution‘ section in the

问题贼难发现，但又贼简单解决： 1、问题描述 > FUNCTION leader.sum does not exist. Check the ‘Function Nam

太过爱你忘了你带给我的痛/ 2024年04月06日 14:52/ 0 赞/ 68 阅读

相关 Function expressions are not supported in decorators changing the function ... exported function.

ionic4 angular8 打包报错： ERROR in src/app/pages/user/user.service.ts(30,28): Error during

女爷i/ 2023年06月16日 02:00/ 0 赞/ 12 阅读

相关 HMAC and the Pseudorandom Function

> The TLS record layer uses a keyed Message Authentication Code (MAC) to protect mess

r囧r小猫/ 2022年10月29日 10:26/ 0 赞/ 14 阅读

相关 HDU 2824 The Euler function (欧拉函数)

The Euler function Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K

雨点打透心脏的1/2处/ 2022年03月29日 05:48/ 0 赞/ 150 阅读

相关 The Euler function

题目描述： Problem Description The Euler function phi is an important kind of function in n

﹏ヽ暗。殇╰゛Y/ 2022年03月18日 02:50/ 0 赞/ 136 阅读

相关 project euler Problem 13

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] str="""37107287533902102

素颜马尾好姑娘i/ 2022年01月16日 03:24/ 0 赞/ 173 阅读

相关 hdu2824 The Euler function O(n)求欧拉函数

hdu2824 The Euler function O(n)求欧拉函数 1 include <bits/stdc++.h> 2 define ll l

我就是我/ 2021年12月14日 12:07/ 0 赞/ 204 阅读

相关 Project Euler：Problem 1

problem: Multiples of 3 and 5 If we list all the natural numbers below 10 that are m

快来打我*/ 2021年11月09日 23:36/ 0 赞/ 248 阅读

相关 hdu 2824 The Euler function

hdu 2824 The Euler function 题意源代码题意给定两个数a,b,求[a,b]区间欧拉函数的和 ps：欧拉

柔光的暖阳◎/ 2021年10月13日 01:33/ 0 赞/ 210 阅读

相关 HDU - 6322 - Problem D. Euler Function 【欧拉函数 + 规律】题解

目录 1.题目 2.代码 1.题目 In number theory, Euler’s totient fu

叁歲伎倆/ 2021年07月25日 00:07/ 0 赞/ 338 阅读