题意
给出一个数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; }
相关推荐
本书为潘承洞院士写的初等数论的入门读物,每章后都有大量的习题供读者练习。
希尔伯特1897年向德国数学会提交的《数论报告》用新的统一的观点,将以往代数数论的知识熔为一个整体。他抓住了互反律这个中心,利用范数剩余记号将高斯古典互反律表示成简单优美的形式: ,从而猜测到高斯互反律的...
哈代数论本书是数论领域的一部传世名著,成书于作者在牛津大学、剑桥大学等学校授课的讲义。书中从各个不同角度对数论进行了阐述,内容包括素数、无理数、同余、费马定理、连分数、不定式、二次域、算术函数、分化等...
数论讲义和数论pdf,从网上找到的教材,觉得还不错,希望对大家有帮助
数论讲义, 数论是纯粹数学的分支之一,主要研究整数的性质。整数可以是方程式的解(丢番图方程)。有些解析函数(像黎曼ζ函数)中包括了一些整数、质数的性质,透过这些函数也可以了解一些数论的问题。透过数论也...
经典初等数论例题100例以及初等数论定理的证明
潘氏兄弟继《初等数论》、《代数数论》之后的又一大倾力贡献,是数论爱好者的必修之课。
这是一个初步介绍数论知识的课件 这是一个真正数论的开始
数论作为密码学的重要的基础知识,学习数论具有重要的意义。
这是一套完整的数论学习教材,可供C++数论初学者学习,里面内容丰富,通俗易懂。
根据颜远松《计算数论》一书,本书为计算机信息安全专业的必修课程,本门课程有大量晦涩难懂的算法,计算量大,特别集中在2.3节大整数分解和2.4节离散对数两章,本应用实现并集成了大整数分解的5个算法和离散对数的...
学习数论,算法分析的必备知识,快下载初等数论
初等数论100例
数论习题答案,因为数论的习题较难,所以当年就收藏了这个!
数论基础知识,初等数论(潘承洞,潘承彪).pdf
数论基础及其应用 作者:沈忠华 编著 出版时间:2015年版 内容简介 《数论基础及其应用》为数学与密码学交叉学科的特色教材,内容包括整除理论、同余、连分数、同余方程、原根。《数论基础及其应用》以数论知识为...
数论作为密码学重要的基础入门课程,这本书十分简单易懂。
初等数论(第三版)闵嗣鹤 严士健 数论习题答案(部分)
初等数论习题解答第三版
将要讨论在ACM程序设计竞赛中出现比较多的一类问题:数论问题。由于数论问题涉及的数学知识比较多、比较深奥,不能在短短的一章中全部予以介绍,只能通过介绍一些案例来说明常见的数论问题。