前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >uva 11426 欧拉函数的运用

uva 11426 欧拉函数的运用

作者头像
用户2965768
发布2019-08-01 10:45:02
3250
发布2019-08-01 10:45:02
举报
文章被收录于专栏:wym

题意: 求 n 以内gcd( i , j ) i < j 的和的个数。

n 的欧拉函数值 表示 小于 n 与 n 互质的数的个数。

对于互质的两个数 a,b (a<b<=n), gcd(a,b) = 1 是显然的。

对 b 而言互质的数有 fai(b) = m个 ,那么b 的贡献就是 m。如果是 2*b呢? 那贡献就是2*m

因为将与 b 互质的m个数都乘2, 就得到 m 个 gcd(2*a,2*b) = 2的数

但2*b不仅仅有 2*m个,因为它也可以通过别的数相乘得到 。那么只需要求出每个数的欧拉函数,

再对 i * j 下标累加 j * fai(i) 个贡献就行,j从1倍一直到小于maxn。

求出的是 i 以内的gcd()和,前 i 项gcd() 和累加就行。

代码语言:javascript
复制
//uva 11426 欧拉函数的运用 
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 4000051;
bool is_prime[maxn];
int prime[maxn],phi[maxn];
ll a[maxn];
void getphi(){
	memset(is_prime,0,sizeof(is_prime));
	phi[1] = 1;
	for(int i=2;i<maxn;i++){
		if(!is_prime[i]){
			prime[++prime[0]] = i;
			phi[i] = i-1;
		}
		for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){
			is_prime[prime[j]*i] = 1;
			if(i%prime[j]==0){
				phi[i*prime[j]] = phi[i]*prime[j];
			}else{
				phi[i*prime[j]] = phi[i]*(prime[j]-1);
			}
		}
	}
}
void solve(){
	getphi();
	for(int i=2;i<maxn;i++){
		for(int j=1;j*i<maxn;j++){
			a[j*i]+=j*phi[i];
		}
	}
	for(int i=1;i<maxn;i++)
		a[i]+=a[i-1];
}
int main() {
	solve();
	int n;
	while(scanf("%d",&n)&&n){
		printf("%lld\n",a[n]);
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年07月14日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档