Diophantus of Alexandria
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 856 Accepted Submission(s): 326
called diophantine equations. One of the most famous diophantine equation is x^n + y^n = z^n. 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:
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:
1 / 6 + 1 / 12 = 1 / 4
1 / 8 + 1 / 8 = 1 / 4
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?
n. Terminate each scenario with a blank line.
2 4 1260
Scenario #1: 3 Scenario #2: 113
这个题个人感觉不难，属于比较基础的数论了吧。。
我是这样思考的：
可以假设x=n+k
那么问题变为了1/n-1/(n+k)有多少分子为1的可能情况
化下简：k/(n*(n+k))-------->k/(n^2+nk)
那么分子要为1，必然的，分母一定是k的倍数
而注意到nk一定是k的倍数，所以关键还是看n^2
那么问题进一步转化为有多少k可以整除n^2
在说白一点，就是求n^2的约数个数。
但是由于这个题要求了x<=y所以最后求出来的约束个数要+1在除以2
我的代码：
#include<stdio.h>
#include<math.h>
#include<string.h>
int prime[40000];
bool flag[40000];
void init()
{
__int64 i,j,num=0;
for(i=2;i<40000;i++)
{
if(!flag[i])
{
prime[num++]=(int)i;
for(j=i*i;j<40000;j=j+i)
flag[j]=true;
}
}
}
void solve(int n,int CASE)
{
int i;
int fac[100],num=0;
memset(fac,0,sizeof(fac));
for(i=0;prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==0)
{
n=n/prime[i];
num++;
fac[num]++;
while(n%prime[i]==0)
{
n=n/prime[i];
fac[num]++;
}
}
if(n==1)
break;
}
if(n>1)
{
num++;
fac[num]++;
}
for(i=1;i<=num;i++)
fac[i]=fac[i]*2;
int ans=1;
for(i=1;i<=num;i++)
ans=ans*(fac[i]+1);
ans=(ans+1)/2;
printf("Scenario #%d:\n",CASE);
printf("%d\n",ans);
}
int main()
{
int n,t,T;
init();
scanf("%d",&T);
for(t=1;t<=T;t++)
{
scanf("%d",&n);
solve(n,t);
printf("\n");
}
return 0;
}