(lightoj - 1236) pairs forming LCM (prime unique decomposition theorem)

Topic link ：Pairs Forming LCM - LightOJ 1236 - Virtual Judge

Chinese question meaning ： Given a n Please lcm(a,b) Number to number ,lcm Represents the least common multiple , And （a,b） and （b,a） Treat as the same number pair .

analysis ： set up n=p1^n1+p2^n2+……+pm^nm（m It's a subscript ）

be a and b They can be expressed as

a=p1^a1+p2^a2+……+pm^am

b=p1^b1+p2^b2+……+bm^bm

Easy to know , if n=lcm(a,b), Then there are max(ai,bi)=ni, That is to say for n A qualitative factor of p,a and b contains p The maximum value of the power of the factor is equal to n contains p The power of the factor , That's for everyone pi factor ,ai and bi One of them must be ni, The other is 0~ni Any number in , So there is 2*(ni+1)-1=2*ni+1（ Because both are ni It's a kind of emptying ）, But contentment a<=b The number of cases except a=b=n This is not the case , Everything else is satisfaction a<b The number of cases is equal to a>b The number of cases , In addition to (n,n) Numbers other than this pair are divided by 2 that will do , That is to say (cal(n)-1)/2+1, Then add (n,n) In this case .

Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e7+9;
bool vis[N];
int prime[N],cnt;
void init()
{
	for(int i=2;i<N;i++)
	{
		if(!vis[i]) prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<N;j++)
		{
			vis[i*prime[j]]=true;
			if(i%prime[j]==0) break;	
		}
	}
}
ll cal(ll n)
{
	ll ans=1;
	for(int i=1;i<=cnt&&prime[i]*prime[i]<=n;i++)
	{
		ll count=0;
		while(n%prime[i]==0)
		{
			n/=prime[i];
			count++;
		}
		ans*=(2*count+1);
	}
	if(n>1) ans*=(2*1+1);// also n This is the prime factor 
	return ans; 
}
int main()
{
	init();
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		ll n;
		scanf("%lld",&n);
		printf("Case %d: %lld\n",_,cal(n)/2+1);
	}
	return 0;
}