数论
约数
试除法求约数 给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<int> get_divisors(int n){
vector<int> 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 x;
cin>>x;
auto res = get_divisors(x);
for(auto t:res) cout << t << " ";
cout << endl;
}
return 0;
}
约数个数
给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int main(){
int n;
cin>>n;
unordered_map<int,int> primes;
while(n--){
int x;
cin>>x;
for(int i=2;i<=x/i;i++){
while(x%i==0){
x/=i;
primes[i]+=1;
}
}
if(x > 1) primes[x]++;
}
ll res = 1;
for(auto prime:primes) res = res * (prime.second + 1) % mod;
cout << res << endl;
return 0;
}
约数之和
给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 10^9+7 取模。
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int main(){
int n;
cin>>n;
unordered_map<int,int> primes;
while(n--){
int x;
cin>>x;
for(int i=2;i<=x/i;i++){
while(x%i==0){
x/=i;
primes[i]+=1;
}
}
if(x > 1) primes[x]++;
}
ll res = 1;
for(auto prime:primes){
int p = prime.first, a = prime.second;
ll t = 1;
while(a--) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
欧几里得算法求最大公约数
给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。
#include<iostream>
using 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;
cin >> a >> b;
cout << gcd(a,b) << endl;
}
return 0;
}
