Would You like to Share!

代码:

POJ 2917题解题报告 数学题
原题描述：
Diophantus of Alexandria
Time Limit: 1000MS                Memory Limit: 65536K
Total Submissions: 2298                Accepted: 669
Description
Diophantus of Alexandria was an Egypt mathematician living in Alexandria. He was one of the first mathematicians to study equations where variables were restricted to integral values. In honor of him, these equations are commonly called Diophantine equations. One of the most famous Diophantine equation is xn + yn = zn. Fermat suggested that for n > 2, there are no solutions with positive integral values for x, y and z. A proof of this theorem (called Fermat’s last theorem) was found only recently by Andrew Wiles.
Consider the following Diophantine equation:
(1)
Diophantus is interested in the following question: for a given n, how many distinct solutions (i. e., solutions satisfying x ≤ y) does equation (1) have? For example, for n = 4, there are exactly three distinct solutions:

Clearly, enumerating these solutions can become tedious for bigger values of n. Can you help Diophantus compute the number of distinct solutions for big values of n quickly?
Input
The first line contains the number of scenarios. Each scenario consists of one line containing a single number n (1 ≤ n ≤ 109).
Output
The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Next, print a single line with the number of distinct solutions of equation (1) for the given value of n. Terminate each scenario with a blank line.
Sample Input
2
4
1260
Sample Output
Scenario #1:
3

Scenario #2:
113
Source
TUD Programming Contest 2006, Darmstadt, Germany

题目大意：
等式 1/x + 1/y = 1/n  x,y,n都为正整数且x<y；
给定n值，输出有多少对这样的x,y;
题意理解
此题主要是时间上要求很严格。不能直接用遍历（1/y = (x - n)/(x*n) 遍历判断x*n能否被（x - n）整除），这样时间不够用。

所以，采用数学公式直接求解，可将此等式转换为 （x - z）(y - z) = z^2  这样就是求Z^2的约数中小于等于z的个数（即问题的答案）；

到这里，求一个数的约数的个数有一个算法。就是先求一个素数表，将这个数逐一试除。

由于，Z取到10^9,那么直接求(10^9)^2将会越界（int）。并且时间上也很难过去。

Z^2所得的完全分解表每一项的个数应该是Z所得的完全分解表的对应项的2倍；
在根据 Yn = X 1^a1 *X2^a2 * …*Xn^an; Yn的约数个数等于（a1 + 1）(a2 + 1)…(an + 1)；（对每一项Xn有an种选法）（1）

这样就先求的Z的分解式，将每一项×2就是Z^2对应的个数。在根据公式（1）就求得Z^2的约数res，而小于Z的约数 = （res + 1）/2
题目的主要考察点:
1.        数学分析能力。（公式的推导）
2.        基础小程序的熟练程度。（求小于n 的素数。分解一个数）
数据范围：
题目数据范围： 1=<N <= 10^9
题目陷阱：
需要注意的地方：
素数表只需求到Sqrt(N)即可；（可节省很多时间）
解题思路：
根据以上分析：
1.先打出32000以内的素数表。（Sqrt(10^2) < 32000）
2.对N进行分解，将每一项的个数存到数组num[]中；
3.利用res *= (2*num + 1) 求出约数个数，最后输出（res + 1）/2;
AC代码：[code]
#include<stdio.h>
#include<math.h>
bool flag[33200]= {0};
int pri[5000];
int prime(int n)
{
n++;
n /= 2;
int i,k,kk;
pri[0] = 2;
pri[1] = 3;
int num = 2;
for(i = 3; i<n; i+=2)
{
for(k = 0; k< 2; ++k)
{
int temp = (i+k)*2 - 1;
if(flag[temp] == 0)
{
pri[num++] = temp;
for(kk = temp; kk< 2*n; kk+=temp)
{
flag[kk] = 1;
}
}
}
}
return num; //素数个数
}

int reduce(int pN,int n)
{

int i,index = 0;
int num[200]= {0};  //记录每个Xn的an个数
for(i = 0; i < pN; ++i)
{
if(n == 1) break;
if(pri*pri>n) //如果n是一个大于sqrt(n)的素数
{
num[index++] = 1;
break;
}
int k = 0;
while(n % pri == 0)
{
k++;
n /= pri;
}
if(k != 0)
num[index++] = k;
}
int res = 1;
for(i=0; i<index; i++)
{
res *= (2*num+1);
}
return res;
}

int main()
{
int casN,cas,N;
scanf(”%d”,&casN);
int pN = prime(32000);
for(cas = 1; cas <= casN; cas++)
{
scanf(”%d”,&N);
int res = reduce(pN,N);
printf(”Scenario #%d:\n%d\n\n”,cas,(res+1)/2);
}
return 0;
}