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