约数,因数。
整数a除以整数b(b≠0) 除得的商正好是整数而没有余数,我们就说a能被b整除,或b能整除a。a称为b的倍数,b称为a的约数。
试除法(从小到大输出):
同质数的试除法思想类似,如果d|n,那么(n/d)|n,即约数是成对出现的,因此只需要枚举到n1/2就可以了。
1 void division(int x) 2 { 3 vector<int> res; 4 for(int i = 1;i <= x/i;++i) 5 { 6 if(x % i == 0) 7 { 8 res.push_back(i); 9 if(i != x/i) 10 res.push_back(x/i); 11 } 12 } 13 sort(res.begin(),res.end()); 14 for(auto c:res) 15 cout << c << " "; 16 cout << endl; 17 }
约数个数:
1 #include <iostream> 2 #include <unordered_map> 3 using namespace std; 4 unordered_map<int,int> prime; 5 const int mod = 1e9 + 7; 6 7 void division(int x) 8 { 9 for(int i = 2;i <= x/i;++i) 10 { 11 while(x % i == 0) 12 { 13 x /= i; 14 prime[i]++; 15 } 16 } 17 if(x > 1) 18 prime[x]++; 19 } 20 21 int main() 22 { 23 int n; 24 cin >> n; 25 while(n--) 26 { 27 int x; 28 cin >> x; 29 division(x); 30 } 31 long long res = 1; 32 for(auto c:prime) 33 res = (res * (c.second + 1)) % mod; 34 cout << res << endl; 35 return 0; 36 }
约数之和:
1 #include <iostream> 2 #include <unordered_map> 3 using namespace std; 4 unordered_map<int,int> prime; 5 const int mod = 1e9 + 7; 6 7 void division(int x) 8 { 9 for(int i = 2;i <= x/i;++i) 10 { 11 while(x % i == 0) 12 { 13 x /= i; 14 prime[i]++; 15 } 16 } 17 if(x > 1) 18 prime[x]++; 19 } 20 21 int main() 22 { 23 int n; 24 cin >> n; 25 while(n--) 26 { 27 int x; 28 cin >> x; 29 division(x); 30 } 31 long long res = 1; 32 for(auto c:prime) 33 { 34 int p = c.first,a = c.second; 35 long long tmp = 1; 36 while(a--) 37 tmp = (tmp * p + 1) % mod ;//秦九韶 38 res = (res * tmp) % mod; 39 } 40 cout << res << endl; 41 return 0; 42 }