注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

HDU 1299数论 求N×N的因子数  

2014-05-07 15:43:17|  分类: ACM/C/C++/OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题意:

给你一个正整数n(n<10^9),问有多少种 x,y 的组合,满足1/n=1/x+1/y;

思路:(毫无疑问x>n y>n)

先设定x,1/y=1/n-1/x     =>   1/y=(x-n)/(n*x); ==>y=(n*x)/(x-n);

令 x=n+p 则 原式转化为    y=(n*n+n*p)/p ==> y= n*n/p + n;

唯一要求 y是整数,所以只要 n*n整除p

只要求p的个数就好了。

也就是求n*n的因子个数 (计为sum)

考虑到 x y不能相等 所以 答案=(sum+1)>>1   之所以要+1是 n也是n*n的因子,但是不会重复

所以只要分解n,得p1^a1*p2^a2*p3^a3.........

n*n的分解为p1^(2*a1)*p2^(2*a2)*p3^(2*a3).........

sum=(1+2*a1)*(1+2*a2)*(1+2*a3)*..........

printf(   (sum+1)>>1 );

代码:

#include<iostream>
#include<math.h>
using namespace std;
#define MAXN 100000
int prime[MAXN];
bool vis[MAXN];
int kp=0;
struct Node
{
int p,a;
} ans[100];
int kans;
void getPrime(int n)
{
int i,j;
int sqrtn=sqrt(double(n));
for(i=2;i<=sqrtn;i++)
{
   if(vis[i]==0)
   {
    prime[kp++]=i;
    for(j=2;i*j<n;j++)
     vis[i*j]=1;
   }
}
for(i;i<n;i++)
   if(vis[i]==0)
    prime[kp++]=i;
}
void getCom(int n)   //分解n,保存在ans中,其实不用结构体就可以了
{
int i;
memset(ans,0,sizeof(ans));
kans=0;
for(i=0;i<kp;i++)
{
   if(prime[i]>n)
    break;

   if(n%prime[i]==0)
   {
    ans[kans].p=prime[i];
    while(n%prime[i]==0)
    {
     ans[kans].a++;
   
     n/=prime[i];
    }
    kans++;
   }
}
if(n>1)
{
   ans[kans].p=n;
   ans[kans].a=ans[kans].a+1;
   kans++;
}
}
int work(int n)
{
int i,sum;
getCom(n);
sum=1;
for(i=0;i<kans;i++)
{
   sum*=(1+2*ans[i].a);
}
return ((sum+1)>>1);
}
int main()
{
getPrime(MAXN);
int t,n,tt=0;

while(scanf("%d",&t)!=EOF)
{
   tt=0;
   while(t--)
   {
  
    scanf("%d",&n);
    printf("Scenario #%d:\n%d\n\n",++tt,work(n));
   }
  
}
return 0;
}

  评论这张
 
阅读(55)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018