不知道什么题的题解

多组测试数据，问你满足 \(lcm\left ( x,y\right ) = n\) 的数对 \(\left ( x,y\right )\) 的数量。

由于唯一分解定理，我们不妨令 \(x = p_{1}^{a_1} \times p_{2}^{a_2} \times \cdots \times p_{i}^{a_i}\)，同理， \(y = p_{1}^{b_1} \times p_{2}^{b_2} \times \cdots \times p_{i}^{b_i}\)，那么 \(lcm\left ( x,y\right ) = p_1^{\max\left ({a_1,b_1}\right )}\times p_2^{\max\left ({a_2,b_2}\right )}\times \cdots \times p_n^{\max\left ({a_n,b_n}\right )}\)。

当 \(a_i> b_i\) 时，\(b_i\) 的可选择范围为 $\left [ 0,\max \left ( a_i,b_i\right )\right ] $ 共 \(\max \left ( a_i,b_i\right )+1\) 种；同理当 \(a_i< b_i\) 时，\(a_i\) 也有 \(\max \left ( a_i,b_i\right ) +1\)种选择。

但是 \(a_i=b_i\) 的情况被重复计算了一次，所以对于素数 \(n\)，总共有 \(2\times \max \left ( a_i,b_i \right ) +1\) 种选择。

所以，总共有 \(\prod \left (2\times \max \left ( a_i,b_i \right ) +1\right )\) 对 \(\left ( x,y\right )\)，使得 \(lcm\left ( x,y\right ) = n\)。

如何写代码？对 \(n\) 分解质因数，对每一个质因数带入公式求积即可。

一定要注意的地方

对于这道题的 \(\left ( i,j\right )\)，有了 \(i<j\) 的解就一定有 \(i>j\) 的解。但是题目求的是 \(i\le j\)，所以我们要注意删掉一些解。所以解就应该先加上 \(i=j\) 的 \(1\) 然后再除以 \(2\)。感谢肖子卓同学，你是我的神！

#include<bits/stdc++.h>
using namespace std;
long long T;
bool Is_Prime(int x){
	if(x==1){
		return 0;
	}
	if(x==2){
		return 1;
	}
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}
int main(){
	cin>>T;
	long long cnt=0;
	while(T--){
		long long n;
		cin>>n;
		long long sum=1;
		for(int i=1;i<=n;i++){
			if(n%i==0&&Is_Prime(i)){
				int k=0;
				while(n%i==0){
					n/=i;
					k++;
				}
				sum*=(k*2+1);
			}
		}
		cout<<"Case "<<++cnt<<": "<<(sum+1)/2<<endl;
	}
}

朴素易懂代码。