lightOj 1370 Bi-shoe and Phi-shoe

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70017#problem/A

题意：给你一组数字，让你求欧拉函数的值大于等于它的数的和的最小值
例如：给你1 2 3，f(2)=1;f(3)=2;f(5)=4,因为没有数的欧拉函数的值等于3，
则需要去欧拉函数大于3的数中的最小值

思路：先预处理出1到N的欧拉函数的值，然后对其处理使得欧拉函数是单调不减的，在从N到1求每个欧拉函数对应的原值，这样求的每个存在的欧拉函数对应的原值是最小的。

#include<stdio.h>
#include<string.h>
using namespace std;
const int N=1500000;
int a[N+5];
int b[N+5];
void Init_oula()//预处理求出1到N的欧拉函数的值
{
    int i,j;
    memset ( a,sizeof (a)) ;
    for ( i = 2 ; i <= N ; i ++ )
    {//筛选求a
        if ( ! a[i] )
        {
            for ( j = i ; j <= N ; j += i )
            {
                if ( ! a[j] )
                    a[j ] = j ;
                a[j] = a[j] / i * ( i - 1 ) ;
            }
        }
    }
}
int mmax(int a,int b){
	if(a>b) return a;
	else return b;
}
int main()
{
	int T,n,k,cnt=0;
	long long ans;
    Init_oula();
	memset(b,sizeof(b));
	for(int i=1;i<=N;i++) a[i]=mmax(a[i],a[i-1]);//保证欧拉函数的值是单调不减的
	for(int i=N;i>=1;i--) b[a[i]]=i;
	//for(int i=1;i<=100;i++) printf("%dn",a[i]);
	for(int i=1;i<=N;i++){
		if(b[i]==0){
			int t=i;
			while(b[i]==b[t] && t<=N){
				t++;
			}
			b[i]=b[t];
		}
	}
	//for(int i=1;i<=100;i++) printf("%dn",b[i]);
	b[0]=0;
	scanf("%d",&T);
	while(T--){
		cnt++;
		ans=0;
		scanf("%d",&n);
		while(n--){
			scanf("%d",&k);
			ans+=b[k];
		}
		printf("Case %d: %lld Xukhan",cnt,ans);
	}
    return 0;
}