LightOJ - 1236 Pairs Forming LCM 算数基本定理

//LightOJ - 1236 Pairs Forming LCM 
//算数基本定理 
#include <bits/stdc++.h>
#define ll long long
#define LL long long
using namespace std;
const int maxn = 10000010;
bool is_prime[maxn];
int prime[maxn/10];
void get_prime(){
	memset(is_prime,0,sizeof(is_prime));
	for(int i=2;i<maxn;i++){
		if(!is_prime[i])prime[++prime[0]] = i;
		for(int j=1;j<=prime[0]&&prime[j]*i<maxn;j++){
			is_prime[prime[j]*i] = 1;
			if(i%prime[j]==0)break;
		}
	}
}

ll getfact(ll x){
	ll ans = 1,tmp = x;
	ll j = 1;
	while(j<prime[0]&&prime[j]*prime[j]<=tmp){
			if(tmp%prime[j]==0){
				ll cnt = 0;
				while(tmp%prime[j]==0)tmp/=prime[j],cnt++;
				ans*=(1+2*cnt);
			}
			j++;
	}
	if(tmp>1)ans*=3;	
	return (ans+1)/2;
}

int main()
{
	get_prime();
	int t,cnt=1;
	ll a;
	scanf("%d",&t);
	while(t--){
		scanf("%lld",&a);
		printf("Case %d: %lld\n",cnt++,getfact(a));
	}
	return 0;
 }