【欧拉函数】最大公约数之和

冷不防 2024-03-22 09:32 57阅读 0赞

**感觉就是欧拉函数裸题啊**

**ez捏**

[问题-最大公约数之和 (51nod.com)][-_ _51nod.com]

题意：

![dab7f49e626644e48f6b058561786a42.png][]

思路：

枚举i肯定超时

考虑枚举gcd

那就是去枚举n的因子p

然后根据题意推一推式子就出来了！

![d9ec55496fe44b95ad093de524d70d8e.jpeg][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    int n;
    
    int phi(int x){
    	vector<pair<int,int> > v;
    	int res=x;
    	for(int i=2;i<=x/i;i++){
    		if(x%i==0){
    			int s=0; 
    			while(x%i==0){
    				x/=i;
    				s++;
    			}
    			v.push_back({i,s});
    		}
    	}
    	if(x>1) v.push_back({x,1});
    	for(int i=0;i<v.size();i++){
    		res=res*(v[i].first-1)/v[i].first;
    	}
    	return res;
    }
    void solve(){
    	cin>>n;
    	set<int> S;
    	for(int i=1;i<=n/i;i++){
    		if(n%i==0){
    			S.insert(i);
    			if(i!=n/i) S.insert(n/i);
    		}
    	}
    	//for(auto it:S) cout<<it<<'\n';
    	//for(int i=1;i<=10;i++) cout<<phi(i)<<'\n';
    	int ans=0;
    	for(auto p:S){
    		ans+=p*phi(n/p);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[-_ _51nod.com]: http://www.51nod.com/Question/Index.html#questionId=803
[dab7f49e626644e48f6b058561786a42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/2236fd5967dd4499a1438ed93d7b7c36.png
[d9ec55496fe44b95ad093de524d70d8e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/f3dbfe507ed3445ca6c5ea1d9a9303cc.png

发表评论取消回复

表情：

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

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

相关阅读

相关欧拉函数

欧拉函数 * 前言 * 求单个欧拉函数值 * 线性求欧拉函数前言在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目在...

曾经终败给现在/ 2024年04月18日 11:45/ 0 赞/ 87 阅读

相关【欧拉函数】最大公约数之和

感觉就是欧拉函数裸题啊 ez捏 [问题-最大公约数之和 (51nod.com)][-_ _51nod.com] 题意： ![dab7f49e626644e48f6b05

冷不防/ 2024年03月22日 09:32/ 0 赞/ 58 阅读

相关欧拉函数 AcWing 873. 欧拉函数

欧拉函数 AcWing 873. 欧拉函数原题链接 [AcWing 873. 欧拉函数][AcWing 873.] 算法标签数学知识欧拉函数思路

绝地灬酷狼/ 2023年09月28日 11:38/ 0 赞/ 130 阅读

相关最大公约数——欧几里得算法最简便

如果a%x=0，我们称x是a的约数（或因数），也称a是x的倍数 a与b的最大公约数，是指一个最大的整数x，使得x同时是a和b的约数，我们将a与b的最大公约数记作`g

旧城等待，/ 2023年01月10日 10:26/ 0 赞/ 123 阅读

相关欧拉函数

欧拉函数对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)

待我称王封你为后i/ 2022年07月29日 08:47/ 0 赞/ 239 阅读

相关欧拉函数

欧拉函数对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)

向右看齐/ 2022年07月19日 01:23/ 0 赞/ 215 阅读

相关欧拉函数

欧拉函数在数论中指的是，对于正整数N,小于或等于N (\[1,N\]),且与N互质的正整数(包括1)的个数，记作φ(n)。以下是欧拉函数的模板 1，直接求φ(n

短命女/ 2022年06月12日 02:58/ 0 赞/ 220 阅读

相关【欧拉函数】

1.1欧拉函数定义首先，需要理解一下什么是欧拉函数，欧拉函数phi(n)的定义为小于等于n且与n互素的整数个数。那么什么是互素呢？互素是指对于两个数a和b，a和b的最大公

雨点打透心脏的1/2处/ 2022年06月09日 00:40/ 0 赞/ 287 阅读

相关欧拉函数

定义在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（φ(1)=1），例如φ(8)=4，因为1,3,5,7均和8互质。通式 ![70][

落日映苍穹つ/ 2022年05月16日 07:58/ 0 赞/ 298 阅读

相关 51nod1040最大公约数之和（欧拉函数）

题面 [传送门][Link 1] 题解这种题目就是推倒推倒 \\\[\\sum\_\{i=1\}^n \\gcd(i,n)=\\sum\_\{i|n\}i\\

向右看齐/ 2021年12月23日 05:31/ 0 赞/ 124 阅读