首页 > 代码库 > 【数论】【欧拉函数】CDOJ1724 为了我们心爱的京电
【数论】【欧拉函数】CDOJ1724 为了我们心爱的京电
京州电子科技大学遭遇废校危机，为了保护我们心爱的学校，N位魔法少女站了出来，她们能做的就是……成为偶像！ 每个魔法少女都拥有一定的人气，他们中的每个人的人气计算方式如下： 假设某个魔法少女的学号为a,学号从1到a-1的共a-1位同学都会为她应援，学号为i的同学能让这位魔法少女增加gcd(a,i)的人气值。 这N位魔法少女最终能否拯救我们的学校呢，试着计算一下他们的总人气值吧！ 
Input
第一行有一个数字N，表示魔法少女的个数 第二行共有N个数字，分别是a[i]，表示第i为魔法少女的学号 其中1<=N<=1e4, 1<=a[i]<=1e6
Output
输出一个数，N位魔法少女的总人气值
对每个数a[i]，枚举所有约数d，答案就是Σphi(d)*a[i]/d，很显然。
#include<cstdio>
using namespace std;
typedef long long ll;
int phi[1000010];
void phi_table(int n){
phi[1]=1;
for(int i=2;i<=n;++i){
if(!phi[i]){
for(int j=i;j<=n;j+=i){
if(!phi[j]){
phi[j]=j;
}
phi[j]=phi[j]/i*(i-1);
}
}
}
}
int n;
ll ans;
void work(int x,int y){
if(y==1){
return;
}
ans+=(ll)(x/y)*(ll)phi[y];
}
int main(){
int x;
phi_table(1000000);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&x);
for(int j=1;j*j<=x;++j){
if(x%j==0){
work(x,j);
if(j!=x/j){
work(x,x/j);
}
}
}
}
printf("%lld\n",ans);
return 0;
}
【数论】【欧拉函数】CDOJ1724 为了我们心爱的京电
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。