第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛 F 等式(数学)


题意:中文题

思路:给你一个1/x + 1/y = 1/n  ,两边同时乘上xyn之后得到式子 nx+ny = xy ,之后通过(自我感觉)非常非常非常敏锐的数学思想,两边同时加上n^2,得到(n-x)*(n-y) = n^2。由此可以看出我们现在要求出的是n^2的所有因子,因为n有1e9所以直接求因子会超时,这个时候我们引入一个非常吊的公式,

所有数都可以化为几个质数次方和相加

p = a1^x1+a2^x2+a3^x3....

那么p的所有因子数sum = (x1+1)*(x2+1)*(x3+1)...(这个东西叫做唯一分解定理)

那么对于p^2 就有(2*x1+1)*(2*x2+1)*(2*x3+1)..

之后我们就可以看出来了,我们先分解质因数,之后搞一下就好了,之后要求出x<= y 的所以最后要/2;

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int prime[maxn];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		cin>>n;
		int cnt = 0;
		memset(prime,0,sizeof(prime));
		for(int i = 2 ; i*i<=n ; i++)
		{
			if(n%i == 0)
			{
				while(n%i ==0)
				{
					prime[cnt]++;
					n = n/i;
				}
				cnt++;
			}
		}
		if(n!=1)
		{
			prime[cnt]++;
			cnt++;
		} 
		int ans = 1;
		for(int i = 0 ; i < cnt;i++)
		{
			ans*=(2*prime[i]+1);
		}
		printf("%d\n",(ans+1)/2);
	}
}

智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告