宁波网站运营优化系统,极速云建站,网站开发公司资质,dw软件主要做什么文章目录 AcWing 869. 试除法求约数题目链接思路CODE AcWing 870. 约数个数题目链接思路CODE AcWing 871. 约数之和题目链接思路CODE AcWing 872. 最大公约数题目链接思路CODE AcWing 869. 试除法求约数
题目链接
https://www.acwing.com/activity/content/problem/content/9… 文章目录 AcWing 869. 试除法求约数题目链接思路CODE AcWing 870. 约数个数题目链接思路CODE AcWing 871. 约数之和题目链接思路CODE AcWing 872. 最大公约数题目链接思路CODE AcWing 869. 试除法求约数
题目链接
https://www.acwing.com/activity/content/problem/content/938/ 思路
基于算术基本定理从最小质数开始往上除直到不含这个因数而和数都是由比它小的质数相乘得来所以所有约束都是质数。
CODE
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;int n;vectorint get_divided(int n){vectorint res;for(int i 1; i n / i; i){if(n % i 0){res.push_back(i);if(i ! n / i) res.push_back(n / i);}}sort(res.begin(), res.end());return res;
}int main()
{cin n;while (n -- ){int a;scanf(%d, a);auto res get_divided(a);for(auto t : res) cout t ;puts();}
}AcWing 870. 约数个数
题目链接
https://www.acwing.com/activity/content/problem/content/939/ 思路
还是基于算术基本定理一个数可以分解为唯一因式 K p 1 a 1 p 2 a 2 . . . p i a i K p1^{a1} p2^{a2} ... pi^{ai} Kp1a1p2a2...piai 那么约数的个数就是公式 ( a 1 1 ) ( a 2 1 ) . . . ( a i 1 ) (a1 1)(a2 1)...(ai 1) (a11)(a21)...(ai1)
CODE
#includevector
#include iostream
#include cstring
#include algorithm
#include unordered_mapusing namespace std;typedef long long ll;const int mod 1e9 7;
int n;int main()
{cin n;unordered_mapint, int primes;while (n -- ){int a;scanf(%d, a);for(int i 2; i a / i; i){while(a % i 0){a / i;primes[i];}}if(a 1) primes[a];}ll res 1;for(auto t : primes) res res * (t.second 1) % mod;cout res endl;
}AcWing 871. 约数之和
题目链接
https://www.acwing.com/activity/content/problem/content/940/ 思路
还是基于算术基本定理 K p 1 a 1 p 2 a 2 . . . p i a i K p1^{a1} p2^{a2} ... pi^{ai} Kp1a1p2a2...piai由这个因式我们可以得到以下公式 N ( p 1 0 p 1 1 . . . p 1 a 1 ) ( p 2 0 p 2 1 . . . p 2 a 2 ) . . . ( p i 0 p i 1 . . . p i a i ) N (p1^0 p1^1 ... p1^{a1})(p2^0 p2^1 ... p2 ^ {a2})...(pi ^ 0 pi ^1 ... pi^{ai}) N(p10p11...p1a1)(p20p21...p2a2)...(pi0pi1...piai)这个公式展开就是每项约数的和。
详细推导可以参考以下视频约数个数与约数之和
CODE
#include iostream
#include cstring
#include algorithm
#include unordered_mapusing namespace std;typedef long long ll;const int mod 1e9 7;
int n;int main()
{cin n;unordered_mapint, int primes;while (n -- ){int a;scanf(%d, a);for(int i 2; i a / i; i){while(a % i 0){a / i;primes[i];}}if(a 1) primes[a];}ll ans 1;for(auto p : primes){ll a p.first, b p.second;ll res 1;while(b--) res (res * a 1) % mod;ans ans * res % mod;}cout ans endl;
}AcWing 872. 最大公约数
题目链接
https://www.acwing.com/activity/content/problem/content/941/ 思路
辗转相除法 具体证明请看 VCR
CODE
#include iostream
#include cstring
#include algorithmusing namespace std;int gcd(int a, int b){return b ? gcd(b, a % b) : a;
}int main()
{int n;cin n;while(n--){int a, b;scanf(%d%d, a, b);cout gcd(a, b) endl;}
}
