C++中约数定理的实例详解
2019/7/10 22:44:30
本文主要是介绍C++中约数定理的实例详解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
C++中约数定理的实例详解
对于一个大于1正整数n可以分解质因数:n = p1^a1*p2^a2*......pk^ak,则n的正约数的个数就是 :(a1+1)*(a2+1)*......*(ak+1)
其中a1、a2、a3…ak是p1、p2、p3,…pk的指数。
用这个定理求一个数的约数个数是非常快的,贴出一道训练题目:
hdu 1492 -求约数的个数
贴出代码:
//约数定理的 #include <iostream> #include <algorithm> #include <iterator> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <vector> #include <queue> #include <set> using namespace std; #define ll long long int main() { // freopen("s.cpp","r",stdin); ll n; while(scanf("%lld",&n) != EOF) { if(!n) break; ll sum = 1; /* x = p1^a1*p2^a2*p3^a3...pk^ak yueshu = (a1+1)*(a2+1)*...*(ak+1)*/ for(ll i = 2; i*i <= n; i++){ int cou = 0; if(n%i==0){ cou = 1; n /= i; while(n%i==0){ cou++; n /= i; } } if(cou != 0){ sum = sum*(cou+1); } } if(n != 1){ sum = sum*2; } if(sum==1 && n==1){ sum = 1; } printf("%lld\n",sum); } return 0; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
这篇关于C++中约数定理的实例详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升