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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1299  

2012-07-02 16:57:11|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1299
这道数论的题,刚开始没做出来,后来看了大牛的推导,才知道额。。

满足 1 / x + 1 / y = 1 / n 的正整数解的对数。 1<= n <= 10^9 ,   1<= x <= y

ms 很强大的一个题目,也是很强的范围,之前有想过这个题目的解法,不过当时太懒,就没敲代码,今天又看到居然不知道怎么做了//..无奈-ing , 看来人老了,记性就不好...

x 、y、n都是正整数,并且 显然,x >= n , y >= n ,现在假设 y = n +k (k为正整数) ,那么带入公式,可以得出 x = (n*(n+k))/k = n*n/k + n; 由于x 是正整数,现在的关键问题就是要求出 n*n/ k 有多少组正整数的可能,显然,所要求的就是 n*n 因子的个数// 问题已经非常接近答案了,但是最后还有一个问题,n<= 10^9 , 那么n*n <= 10^18 ,对于一个这么大的数字怎样才能求出它因子的个数呢?

命题1: 一个正整数 n 可以用素因子唯一表示为 p1^r1 * p2^r2 * ... pk^rk (其中 pi 为素数) , 那么这个数的因子的个数就是,(r1+1)*(r2+1)*...*(rk+1).

如果一个数字 n = p1^r1 * p2^r2 * ... pk^rk ,那么 n*n = p1^r1 * p2^r2 * ... pk^rk   * p1^r1 * p2^r2 * ... pk^rk ,它的因子的个数就是 (2*r1+1)*(2*r2+1)*...*(2*rk+1).

这个问题就转化成了求 n <= 10^9 的素因子的问题,只需要先筛选出 sqrt(10^9) 内的素数,然后用n去试除 sqrt(n) 中的每一个即可,当然,n可能会有大于sqrt(n) 的因子

AC Code:

#include<iostream> #include<cmath> using namespace std; int i,j,num; bool prime[50000]; int pp[10000]; void init() {     memset(prime,true,sizeof(prime));     prime[0] = false;  prime[1] = false;     for(i = 2; i < 25000; i ++)         for(j = 2; i*j < 50000; j ++)             prime[i*j]= false;     num = 0;     for(i = 0; i < 50000; i ++)         if(prime[i] == true)             pp[num++] = i; } int main() {   int T,n,sum,t,e = 1,ll;  init();     scanf("%d",&T);     while(T--)     {         scanf("%d",&n);         sum = 1;         ll = (int)sqrt(n*1.0);         for(i = 0; i < num; i ++)         {             if(pp[i] > ll +1)        break;             t = 0;             while(n%pp[i] == 0)                 t ++,n/= pp[i];             sum *= (t*2+1);         }         if(n > 1)       sum *= 3;         printf("Scenario #%d:\n",e++);         printf("%d\n\n",(sum+1)/2);     }     return 0; }
  评论这张
 
阅读(165)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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