Bi-shoe and Phi-shoe【lightoj1370】——欧拉数
Bamboo Pole-vault is a massively popular sport in Xzhiland. And Master Phi-shoe is a very popular coach for his success. He needs some bamboos for his students,so he asked his assistant Bi-Shoe to go to the market and buy them. Plenty of Bamboos of all possible integer lengths (yes!) are available in the market. According to Xzhila tradition,Score of a bamboo = Φ (bamboo’s length)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Max = 1e6+10;
int phi[Max];
void Init()
{
memset(phi,0,sizeof(phi));
phi[1] = 1;
for(int i = 2;i < Max; i++)
{
if(!phi[i])
{
for(int j = i;j < Max ; j+=i)
{
if(!phi[j]) phi[j] = j;
phi[j] = phi[j]/i*(i-1);
}
}
}
}
int a[Max];
int main()
{
int T,z = 1;
int n;
Init();
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i = 0;i < n; i++) scanf("%d",&a[i]);
sort(a,a+n);
LL ans = 0 ;
for(int i = 0; i < n ; i++)
{
int j = a[i]+1;
while(phi[j]<a[i]) j++;
ans+=j;
}
printf("Case %d: %lld Xukhan",z++,ans);
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |