题目描述：

小象同学在初等教育时期遇到了一个复杂的数学题，题目是这样的：

给定自然数 n，确定关于 x,y,z 的不定方程
Comet OJ解不定方程-素数分解式+递归
的所有自然数解。

当时的小象同学并不会做这道题。多年后，经过高等教育的洗礼，小象同学发现这道题其实很简单。小象同学认为你一定也会做这道题，所以把这道题留给了你。为了便于输出，你不需要输出每一组解 (x,y,z)，你只需要给出解的数量和所有解的 xyz之和对 (10⁹+7)取模的值即可。注意，解的数量不对(10⁹+7)取模。

输入描述：

输入包含多组测试数据。输入的第一行包含一个正整数 T (1≤T≤10⁴)，表示测试数据的组数。接下来依次描述每组测试数据，对于每组测试数据：

仅一行，包含一个非负整数 n(0≤n≤2×10⁹)，含义如题面所示。

输出描述：

对于每组数据，输出一行。若方程有无穷多组自然数解，则在这一行输出 “infty”（不含引号），否则在这一行输出两个整数，其中第一个整数表示方程的解数，第二个整数表示所有解的 xyz之和对 (10⁹+7) 取模的值，这两个整数之间用恰好一个空格隔开，行末不要有多余的空格。

样例输入：

3
6
12
24

样例输出：

0 0
1 12
2 72

核心思路：

方程可化简为：
Comet OJ解不定方程-素数分解式+递归将n/4进行素数分解，然后利用递归枚举y的值，细节见代码。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define mo 1000000007
using namespace std;
typedef long long ll;
const int N=1e5+30;
int pre[N],cnt;//筛出来的素数 
bool vis[N];
ll p[N],nu,n,a1,a2;//p数组存素数因子，nu是p数组大小，a1，a2是要输出的俩数 
int b[N];//b数组是p数组对应素因子的个数 
void xss()//欧拉筛法 
{
	for(int i=2;i<N-10;i++)
	{
		if(!vis[i])
			pre[cnt++]=i;
		for(int j=0;j<cnt&&pre[j]*i<N-5;j++)
		{
			vis[pre[j]*i]=1;
			if(i%pre[j]==0)break;
		}
	}
}
void fun(ll y,int k)//递归求每一种解 
{
	if(n/y<=y)//按照题意，z应该大于y 
		return;
	if(k>=nu)//递归出口 
	{
		a1++;
		a2=(a2+n*(n/y+y))%mo;
		return;
	}
	for(int i=0;i<=b[k];i++)//对于每个素因子，贡献情况有0，1，2....b[k]共b[k]+1种 
	{
		fun(y,k+1);
		y*=p[k];
	}
	return;
}
int main()
{
	xss();
	int T;
	scanf("%d",&T);
	while(T--)
	{
		nu=0;
		a1=0;
		a2=0;
		scanf("%lld",&n);
		double tt=n;
		ll t=ll(sqrt(tt));
		if(t*t==n||(t+1)*(t+1)==n)//如果n是一个自然数的平方，则有无数多种解，令x=根号n，y和z相等即可 
		{
			printf("infty\n");
			continue;
		}
		if(n%4!=0)//n不能被4整除，无解 
		{
			printf("0 0\n");
			continue;
		}
		n>>=2;//n除以4后，n=y*z 
		ll tn=n;
		for(int i=0;i<cnt;i++)//求tn的素数分解式 
		{
			if(tn==1)
				break;
			if(tn%pre[i]==0)
			{
				p[nu]=pre[i];
				b[nu]=0;
				while(tn%pre[i]==0)
				{
					b[nu]++;
					tn/=pre[i];
				}
				nu++;
			}
		}
		if(tn!=1)//如果1e5以内的素数无法将tn分解完全，则余下的tn是一个大于1e5的素数 
		{
			p[nu]=tn;
			b[nu]=1;
			nu++;
		}
		fun(1,0);
		printf("%lld %lld\n",a1,a2);
	}
	return 0;
}

Comet OJ解不定方程-素数分解式+递归