当前位置 博文首页 > skymeteorite:hdu1299素因子分解
题意:
求方程1/x+1/y=1/n的解的个数 1/3+1/2 与1/2+1/3看作是一组解。
分析:
1/x+1/y = 1/n 设y = n + k;
==>1/x + 1/(n+k)=1/n;
==>x = n^2/k + n;
因为x为整数,k就是n^2的约数。然后对其素因子分解就可以了。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=1e7;
typedef long long LL;
int p[maxn],cnt;
bool prime[maxn];
int fac[1000],tot;
void isprime()
{
cnt=0;
memset(prime,0,sizeof(prime));
for(int i=2;i<maxn;i++)
{
if(!prime[i])
{
p[cnt++]=i;
for(int j=i+i;j<maxn;j+=i) prime[j]=1;
}
}
}
LL fenjie(LL x)
{
tot=0;
memset(fac,0,sizeof(fac));
for(int i=0;i<cnt&&p[i]*p[i]<=x;i++)
{
if(x%p[i]==0)
{
while(x%p[i]==0)
{
fac[tot]++;
x/=p[i];
}
tot++;
}
}
if(x>1)
fac[tot++]=1;
LL ans=1;
for(int i=0;i<tot;i++)
ans=ans*(2*fac[i]+1);
return ans;
}
int main()
{
isprime();
int t,cas=1;
cin>>t;
while(t--)
{
LL n;
cin>>n;
printf("Scenario #%d:\n%lld\n\n",cas++,(fenjie(n)+1)/2);
}
return 0;
}
cs