`
暴风雪
  • 浏览: 388994 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[数论]hdoj 1299

 
阅读更多

题意

      给出一个数n(0<n<10^9)。问有多少种a,b的组合使得1/a+1/b=1/n。

思路

      第一步a,b肯定大于n。设a=n+x,b=n+y。得到n^2=x*y。题目转化为求n^2有多少种分解为两个数乘积的方法。

     第二步,这里有一个定理ai为一个质数。对于一个数字x,x=a1^k1*a2^k2,,,,,*an^kn。则x的因子个数为(k1+1)*(k2+1)*,,,,,*(kn+1)。

     第三步,容易推出x^2的因子个数为(2*k1+1)*(2*k2+1)*,,,,,*(2*kn+1)

     第四步,对于一个完全平方数x,其因子个数为n,则x=ab的组合的个数为(n+1)/2

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int nMax = 100000;
int sum[nMax] = {0};
int prime[nMax]={0};
void make(){
	int i,j;
	for(i=2;i<nMax;i++){
		if(i%2)sum[i]=1;
	}
	int temp=(int)sqrt(nMax);
	for(i=3;i<temp;i++){
		if(sum[i]){
			for(j=i+i;j<=nMax;j+=i){
				sum[j]=0;
			}
		}
	}
	sum[1]=0;sum[2]=1;
	int a=0;
	for(i=0;i<nMax;i++){
		if(sum[i]){
			prime[a]=i;
			a++;
		}
	}
}
int main(){
    int i,ans,b,c,n,tcs,tt;
    cin>>tcs;
    make();
    for(tt = 1; tt <= tcs; tt ++){
        cin>>n;
        ans = 1;
        b = sqrt(n);
        for(i = 0;prime[i] <= b; i ++){
            if(n % prime[i] == 0){
                c = 0;
                while(n%prime[i] == 0){
                    c ++;
                    n /= prime[i];
                }
                ans*=(c * 2 + 1);
            }
        }
        if(n != 1){
            ans *= 3;
        }
        printf("Scenario #%d:\n%d\n\n",tt,(ans+1)/2);
    }
    return 0;
}

 

0
0
分享到:
评论

相关推荐

    HDOJ题目分类 HDOJ题目分类

    4. **数学问题**:组合数学、数论、几何、概率等。 5. **应用领域**:字符串处理、网络流、模拟、游戏理论等。 【压缩包子文件的文件名称列表】:HDOJ题目分类.pdf 这个PDF文档很可能包含了HDOJ平台上所有题目的...

    HDOJ.rar_HD_HDOJ

    5. **数学问题**:数论(质因数分解、同余方程、模运算)、组合数学(排列组合、鸽巢原理)、概率论等。 6. **字符串处理**:模式匹配(KMP、Boyer-Moore、Rabin-Karp)、最长公共前后缀、编辑距离等。 7. **计算...

    ACM HDOJ 课件

    1. **简单数学**:这是编程的基础,包括但不限于整数、浮点数运算,数论(如质数、最大公约数、最小公倍数),排列组合等。这些基础知识在解决许多实际问题时都至关重要。 2. **组合数学**:组合数学是研究有限集合...

    HDOJ暑期多校联赛第三场

    【HDOJ暑期多校联赛第三场】是2013年举办的一场面向广大编程爱好者的在线竞赛,由IOI(国际奥林匹克信息学竞赛)的冠军CLJ设计题目,旨在提升参赛者的信息学和算法解决能力。这次比赛涵盖了丰富的编程和算法知识点,...

    HDOJ.zip_hduoj100题

    【HDOJ.zip_hduoj100题】是一个压缩包文件,包含了HDUOJ(杭州电子科技大学在线评测系统)的约100道编程练习题目及其源代码。这个资源对于想要提升编程技能,尤其是对算法和数据结构有深入学习需求的程序员来说,是...

    杭电 2000到2050 acm的AC解题报告

    4. **数学应用**:包括数论、组合数学、线性代数、概率统计等,很多问题需要用到数学思维来简化问题并找到解答。 5. **编程技巧**:如何优化代码,提高运行效率,减少内存消耗,如位运算、递归优化、循环展开等。 ...

    (lecture_02)简单数学题090223.ppt

    对于这类问题,避免暴力枚举,尝试归纳总结,有时还需要用到数论知识。 总的来说,ACM竞赛中的数学题需要选手具备扎实的数学基础、灵活的算法运用能力和对数据规模敏感的洞察力。通过不断练习和学习,可以提升这些...

    ACM_HDU:在 hdoj 中解决了我的 acm 问题的一部分

    8. **数学基础**:组合数学、数论、几何等,许多题目需要一定的数学思维。 9. **字符串处理**:KMP算法、Manacher's Algorithm等。 在"ACM_HDU-master"中,我们可以期待看到如何运用这些知识去解决具体问题的实例...

    杭电2010ACM培训ppt

    同时,由于是杭州电子科技大学的内部培训资料,其中可能还包含了历年杭电(HDOJ,杭州电子工业学院在线评测系统)的题目解析和解题思路,这对于熟悉HDOJ题库和提升解题能力非常有帮助。 总的来说,《杭电2010ACM...

    杭电acm课件

    这份压缩包中的【HDOJ课件】很可能包含了杭电在线判题系统(HDOJ,即杭州电子科技大学在线评测系统)的讲义、PPT演示文稿和其他相关教学资料。这些课件通常会涵盖以下关键知识点: 1. **基础算法**:包括排序(快速...

    杭电acm1201-1250

    在ACM竞赛中,题目类型广泛,可能涵盖数学问题、图形学、搜索算法、动态规划、贪心策略、排序算法、字符串处理、数论等多个领域。对于这些题目,解答通常会包含以下部分: 1. **问题描述**:简述问题的背景和目标,...

    ACM离线题库(1200道)

    8. **数学问题**:数论、组合数学、概率统计等。 总的来说,"ACM离线题库(1200道)" 是一个宝贵的资源,它可以帮助参赛者通过大量的实践来磨炼编程技巧,理解并掌握各种算法,为参与ACM竞赛做好充分的准备。

    杭电ACM训练PPT

    12. **hdoj_offline_2008_07_16**:这可能是某个特定的离线比赛题目集,包含当年杭州电子科技大学在线评测系统(HDOJ)的题目。 这些PPT内容丰富,覆盖了算法和数学的多个方面,是准备编程竞赛和提升算法能力的宝贵...

    acm资料大全

    7. **训练方法**:通过在线oj(Online Judge,如Codeforces、LeetCode、HDOJ等)进行模拟练习,提升解决问题的速度和准确性。同时,分析和理解别人优秀的解决方案也是提高自己的重要途径。 8. **课件内容**:压缩包...

    杭电 acm 入门ppt

    PPT可能还会推荐一些在线编程平台,如LeetCode、HDOJ(杭电在线评测系统)等,供学习者进行实战训练。 最后,PPT可能会提到团队合作和心理素质的培养,因为ACM竞赛不仅是技术的比拼,也是团队协作能力和心理承受力...

    ACM课件.rarACM课件.rar

    5. 数学知识:组合数学、数论、离散数学等在解决某些复杂问题时起着关键作用。 6. 字符串处理:模式匹配(KMP、Boyer-Moore)、字符串函数(Rabin-Karp、Z-Algorithm)等技术在文本处理问题中不可或缺。 7. 动态规划...

    ACM算法基础(必备)

    熟练掌握这些基础知识后,你需要通过不断练习,参与在线判题平台(如LeetCode、Codeforces、HDOJ等)的题目,提高解决问题的能力。同时,学习他人的解题思路,了解如何在限制时间内构思、编写和调试代码,也是提升...

    acm培训的资料!!!!!

    随着ACM竞赛难度的提升,需要掌握更高级的算法,如字符串匹配(KMP、Boyer-Moore、Rabin-Karp等)、网络流、数学建模(组合数学、线性代数、数论)、最优化问题(线性规划、分支定界法)等。这些算法往往能解决复杂...

    杭州电子科技大学ACM评判系统离线题库

    【文件名称】:“hdoj离线题库(更新至2223).CHM”是一个帮助文件格式,通常包含组织良好的索引和内容,便于用户查找和阅读题目。CHM文件是Microsoft的 Compiled HTML Help 格式,它将HTML文档集合打包成一个可搜索...

    acm 过程中做过的一些习题和解答

    - **题库选择**:选择合适的在线平台进行训练非常重要,如Codeforces、HDOJ、UVA等,这些平台提供了丰富的题目供选手练习。 - **解题策略**:学会高效地分析问题,明确题目要求,确定使用的算法和数据结构。在编码...

Global site tag (gtag.js) - Google Analytics