题意
给出一个数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; }
相关推荐
4. **数学问题**:组合数学、数论、几何、概率等。 5. **应用领域**:字符串处理、网络流、模拟、游戏理论等。 【压缩包子文件的文件名称列表】:HDOJ题目分类.pdf 这个PDF文档很可能包含了HDOJ平台上所有题目的...
5. **数学问题**:数论(质因数分解、同余方程、模运算)、组合数学(排列组合、鸽巢原理)、概率论等。 6. **字符串处理**:模式匹配(KMP、Boyer-Moore、Rabin-Karp)、最长公共前后缀、编辑距离等。 7. **计算...
1. **简单数学**:这是编程的基础,包括但不限于整数、浮点数运算,数论(如质数、最大公约数、最小公倍数),排列组合等。这些基础知识在解决许多实际问题时都至关重要。 2. **组合数学**:组合数学是研究有限集合...
【HDOJ.zip_hduoj100题】是一个压缩包文件,包含了HDUOJ(杭州电子科技大学在线评测系统)的约100道编程练习题目及其源代码。这个资源对于想要提升编程技能,尤其是对算法和数据结构有深入学习需求的程序员来说,是...
【HDOJ暑期多校联赛第三场】是2013年举办的一场面向广大编程爱好者的在线竞赛,由IOI(国际奥林匹克信息学竞赛)的冠军CLJ设计题目,旨在提升参赛者的信息学和算法解决能力。这次比赛涵盖了丰富的编程和算法知识点,...
4. **数学应用**:包括数论、组合数学、线性代数、概率统计等,很多问题需要用到数学思维来简化问题并找到解答。 5. **编程技巧**:如何优化代码,提高运行效率,减少内存消耗,如位运算、递归优化、循环展开等。 ...
对于这类问题,避免暴力枚举,尝试归纳总结,有时还需要用到数论知识。 总的来说,ACM竞赛中的数学题需要选手具备扎实的数学基础、灵活的算法运用能力和对数据规模敏感的洞察力。通过不断练习和学习,可以提升这些...
8. **数学基础**:组合数学、数论、几何等,许多题目需要一定的数学思维。 9. **字符串处理**:KMP算法、Manacher's Algorithm等。 在"ACM_HDU-master"中,我们可以期待看到如何运用这些知识去解决具体问题的实例...
同时,由于是杭州电子科技大学的内部培训资料,其中可能还包含了历年杭电(HDOJ,杭州电子工业学院在线评测系统)的题目解析和解题思路,这对于熟悉HDOJ题库和提升解题能力非常有帮助。 总的来说,《杭电2010ACM...
这份压缩包中的【HDOJ课件】很可能包含了杭电在线判题系统(HDOJ,即杭州电子科技大学在线评测系统)的讲义、PPT演示文稿和其他相关教学资料。这些课件通常会涵盖以下关键知识点: 1. **基础算法**:包括排序(快速...
在ACM竞赛中,题目类型广泛,可能涵盖数学问题、图形学、搜索算法、动态规划、贪心策略、排序算法、字符串处理、数论等多个领域。对于这些题目,解答通常会包含以下部分: 1. **问题描述**:简述问题的背景和目标,...
8. **数学问题**:数论、组合数学、概率统计等。 总的来说,"ACM离线题库(1200道)" 是一个宝贵的资源,它可以帮助参赛者通过大量的实践来磨炼编程技巧,理解并掌握各种算法,为参与ACM竞赛做好充分的准备。
12. **hdoj_offline_2008_07_16**:这可能是某个特定的离线比赛题目集,包含当年杭州电子科技大学在线评测系统(HDOJ)的题目。 这些PPT内容丰富,覆盖了算法和数学的多个方面,是准备编程竞赛和提升算法能力的宝贵...
7. **训练方法**:通过在线oj(Online Judge,如Codeforces、LeetCode、HDOJ等)进行模拟练习,提升解决问题的速度和准确性。同时,分析和理解别人优秀的解决方案也是提高自己的重要途径。 8. **课件内容**:压缩包...
PPT可能还会推荐一些在线编程平台,如LeetCode、HDOJ(杭电在线评测系统)等,供学习者进行实战训练。 最后,PPT可能会提到团队合作和心理素质的培养,因为ACM竞赛不仅是技术的比拼,也是团队协作能力和心理承受力...
5. 数学知识:组合数学、数论、离散数学等在解决某些复杂问题时起着关键作用。 6. 字符串处理:模式匹配(KMP、Boyer-Moore)、字符串函数(Rabin-Karp、Z-Algorithm)等技术在文本处理问题中不可或缺。 7. 动态规划...
熟练掌握这些基础知识后,你需要通过不断练习,参与在线判题平台(如LeetCode、Codeforces、HDOJ等)的题目,提高解决问题的能力。同时,学习他人的解题思路,了解如何在限制时间内构思、编写和调试代码,也是提升...
随着ACM竞赛难度的提升,需要掌握更高级的算法,如字符串匹配(KMP、Boyer-Moore、Rabin-Karp等)、网络流、数学建模(组合数学、线性代数、数论)、最优化问题(线性规划、分支定界法)等。这些算法往往能解决复杂...
【文件名称】:“hdoj离线题库(更新至2223).CHM”是一个帮助文件格式,通常包含组织良好的索引和内容,便于用户查找和阅读题目。CHM文件是Microsoft的 Compiled HTML Help 格式,它将HTML文档集合打包成一个可搜索...
- **题库选择**:选择合适的在线平台进行训练非常重要,如Codeforces、HDOJ、UVA等,这些平台提供了丰富的题目供选手练习。 - **解题策略**:学会高效地分析问题,明确题目要求,确定使用的算法和数据结构。在编码...