数论
欧拉函数
给定 n 个正整数 ai，请你求出每个数的欧拉函数。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
int n;
cin >> n;
while(n--){
int a;
cin >> a;
int res = a;
for(int i = 2;i <= a/i;i++){
if(a % i == 0){
res = res / i * (i-1);
while(a % i == 0) a/=i;
}
}
if(a > 1) res = res / a * (a-1);
cout << res << endl;
}
return 0;
}
筛法求欧拉函数
给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int n;
int phi[N],primes[N],cnt;
bool st[N];
typedef long long ll;
ll ans;
ll get_eulers(int n){
phi[1] = 1;
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++] = i;
phi[i] = i - 1;
}
for(int j=0;primes[j]<=n/i;j++){
st[primes[j] * i] = true;
if(i % primes[j] == 0){
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
for(int i=1;i<=n;i++){
ans += phi[i];
}
return ans;
}
int main(){
cin >> n;
cout << get_eulers(n) << 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,pi，对于每组数据，求出 ai^bi mod pi 的值。
核心思路是：预处理出来a^(2^0) a^(2^1) … a^(2^logk)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
// a^k mod p
int qmi(int a,int k,int p){
int res = 1;
while(k){
if(k & 1) res = (ll)res * a % p;
k >>= 1;
a = (ll)a * a % p;
}
return res;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,k,p;
scanf("%d%d%d",&a,&k,&p);
printf("%d\n",qmi(a,k,p));
}
return 0;
}
