频道栏目
首页 > 资讯 > 其他 > 正文

等式(数论/唯一分解定理)

18-03-28        来源:[db:作者]  
收藏   我要投稿

等式(数论/唯一分解定理)

题目描述

给定n,求1/x + 1/y = 1/n (x<=y)的解数。(x、y、n均为正整数)

 

输入描述:

在第一行输入一个正整数T。
接下来有T行,每行输入一个正整数n,请求出符合该方程要求的解数。
(1<=n<=1e9)

输出描述:

输出符合该方程要求的解数。

 

首先明白一个定理:唯一分解定理(算数基本定理)


? ? ? ? ? ? 任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3......Pnan,这里P1<><>


证明可以去网上搜;


<>

? ? ? ? ? ? ? ? 接下来有几个重要的推论:


? ? ? ? ? ? ? ? ?(1)一个大于1的正整数N,如果它的标准分解式为
?:

????????????????????????n=?p1^a1 * p2^a2 * p3^a3 * p4^a4 ......? * pk^ak ????????????????????????,那么它的正因数个数为(1+a1)* (1+a2) * (1+a3) * (1+a4) * .......* (1+ak);
? ? ? ? ? ? ? ? ? 
(2)此外还可证明根号2是无理数等等。 (3)证明素数个数无限。 ? ? ? ? 在本题中我们用的是推论一: ? ? ? ? ? ? ? ? ? 我们设 n+a=x, n+b=y,带入等式化简后得n^2=a*b且b>=a;


? ? ? ? ? ? ? ? ? 那么问题就转换成求n^2有多少对因子;



? ? ? ? ? ? ? ? ? 可以用短除法可以将n分解p1^a1 * p2^a2 * p3^a3 * p4^a4 ......? * pk^ak(pi为质数)的形式。



? ? ? ? ? ? ? ? ? 那么n^2=p1^(2*a1) * p2^(2*a2) * p3^(2^a3) * p4^(2*a4)? *..... * pk^(2*ak);



? ? ? ? ? ? ? ? ? 可以推出n^2所有的因子个数sum为(1+2*a1)* (1+2*a2) * (1+2*a3) * (1+2*a4) * .......* (1+2*ak);



? ? ? ? ? ? ? ? ? 所以结果为(sum+1)/2;? ? ?(sum+1是因为考虑到a==b==n的情况);


代码如下:


#include
int DecompositionFactor(int n);
/*
3
1
20180101
1000000000
输出

1
5
181
*/ 
int main()
{
	int t;
	
	scanf("%d",&t);
	
	while(t--)
	{
		int n;
		
		scanf("%d",&n) ;
		
		int sum = DecompositionFactor(n);    //求出n^2的所有因子的个数 
		
		printf("%d\n",(sum + 1) / 2);
		
	}
	
	
	
	
	return 0;
} 
int DecompositionFactor(int n)
{
	int sum = 1;
	
	for(int i = 2;i*i <= n;i++)
	{
		int count = 0;
		
		while(n%i == 0)
		{
			count++;
			
			n/=i;
		}
		
		sum *= (1 + 2 * count);
	}
	
	if(n != 1)
	sum *= (1 + 2 * 1);
	
	return sum;
}
相关TAG标签
上一篇:windows使用git时出现:warning: LF will be replaced by CRLF如何解决?
下一篇:内核ACPI函数API之acpi_evaluate_integer
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站