[唯一分解定理]Pairs Forming LCM

题目链接：https://vjudge.net/contest/356798#problem/H
题意：
在a,b中(a,b<=n)(1 ≤ n ≤ 1014),有多少组(a,b) (a<b)满足lcm(a,b)==n;
题解：
(注意原作者对于代码的构思，n过大时解决的常见套路)
先来看个知识点：

素因子分解：n = p1 ^ e1 * p2 ^ e2 *…*pn ^ en

for i in range(1,n):

    ei 从0取到ei的所有组合

必能包含所有n的因子。

现在取n的两个因子a,b

a=p1 ^ a1 * p2 ^ a2 *…*pn ^ an

b=p1 ^ b1 * p2 ^ b2 *…*pn ^ bn

gcd(a,b)=p1 ^ min(a1,b1) * p2 ^ min(a2,b2) *…*pn ^ min(an,bn)

lcm(a,b)=p1 ^ max(a1,b1) * p2 ^ max(a2,b2) *…*pn ^ max(an,bn)

哈哈，又多了种求gcd,lcm的方法。

题解：

先对n素因子分解，n = p1 ^ e1 * p2 ^ e2 *…*pk ^ ek，

lcm(a,b)=p1 ^ max(a1,b1) * p2 ^ max(a2,b2) *…*pk ^ max(ak,bk)

所以，当lcm(a,b)==n时，max(a1,b1)==e1,max(a2,b2)==e2,…max(ak,bk)==ek

当ai == ei时，bi可取 [0, ei] 中的所有数 有 ei+1 种情况，bi==ei时同理。

那么就有2(ei+1)种取法,但是当ai = bi = ei 时有重复，所以取法数为2(ei+1)-1=2ei+1。
除了 (n, n) 所有的情况都出现了两次 那么满足a<=b的有 (2ei + 1)) / 2 + 1 个

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+7; //1e14中素数差不多1e6左右
const int NN=1e7+7;//常见套路，就是只遍历到sqrt，代码最后if语句判断一下就好
ll pri[N];
bool vis[NN];
void isprime() {
   
	memset(vis,false,sizeof(vis));
	for(int i=2; i<=NN; i++) {
   
		if(!vis[i]) {
   
			pri[++pri[0]]=i;
		}
		for(int j=1; j<=pri[0] && i*pri[j]<=NN; j++) {
   
			vis[i*pri[j]]=1;
			if(i % pri[j]==0) {
   
				break;
			}
		}
	}
}
// 欧拉筛
int main()
{
   
	isprime();
	ll n;
	int t,cnt=0;
	scanf("%d", &t);
	while(t--) {
   
		ll ans=1;
		scanf("%lld", &n);
		// for中的i<=pir[0]经常漏，要注意！
		for(int i=1; i<=pri[0]&&pri[i]<=sqrt(n); i++) {
   
			if(n%pri[i]==0) {
   
				int e=0;
				while(n%pri[i]==0) {
   
					n/=pri[i];
					e++;
				}
				ans*=(2*e+1);
			}
		}
		//易漏：如果还有素因子，那么必定只有一个，且那个素因子为1次
		if(n>1) 
			ans*=(2*1+1);  
		printf("Case %d: %lld\n",++cnt,(ans+1)/2);
	}
	return 0;
}