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; } (编辑:PHP编程网 - 黄冈站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |