LightOJ 1370 Bi-shoe and Phi-shoe(欧拉函数)
题目链接: #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 3000010;
int T,prime_cnt,n,cases = 0;
int prime[MAX_N / 10],phi[MAX_N],ans[MAX_N];
bitset<MAX_N> bs;
inline void GetPrime() //素数筛
{
bs.set();
prime_cnt = 0;
for(int i = 2; i < MAX_N; i++){
if(bs[i]) { prime[prime_cnt++] = i; }
for(int j = 0; j < prime_cnt && i * prime[j] < MAX_N; j++){
bs[i * prime[j]] = 0;
if(i % prime[j] == 0) break;
}
}
}
inline void GetEuler()
{
GetPrime();
for(int i = 2; i < MAX_N; i++) { phi[i] = i; } // 1不能带进去!和一般的欧拉函数不一样!
for(int i = 0; i < prime_cnt; i++){
for(int j = prime[i]; j < MAX_N; j += prime[i]){
phi[j] = phi[j] / prime[i] * (prime[i] - 1);
}
}
for(int i = 10; i < 100; i++){
printf("phi[%d] = %dn",i,phi[i]);
}
}
inline void init()
{
GetEuler();
memset(ans,0,sizeof(ans));
for(int i = 1; i < MAX_N; i++){
int t = phi[i];
if(t > MAX_N || ans[t]) continue;
ans[t] = i;
}
int pre = INT_MAX;
for(int i = MAX_N - 10 ; i >= 1; i--){
if(ans[i]) { //已经被赋过值了
pre = min(pre,ans[i]);
ans[i] = min(ans[i],pre); //这里特别注意!不能漏了!
}else { //还没被赋值就从后面的赋值结果中找到最小的
ans[i] = pre;
}
}
}
int main()
{
init();
scanf("%d",&T);
while(T--){
scanf("%d",&n);
ll res = 0;
for(int i = 0; i < n; i++){
int t;
scanf("%d",&t);
res += ans[t];
}
printf("Case %d: %lld Xukhan",++cases,res);
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |