acwing算法提高之数学知识--约数个数和欧拉函数

1 介绍

本博客用来记录约数个数和欧拉函数相关的题目。

2 训练

题目1：1291轻拍牛头

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1000010;int n;
int a[N], cnt[N], s[N];int main() {scanf("%d", &n);for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);cnt[a[i]]++;}for (int i = 1; i < N; ++i) {for (int j = i; j < N; j += i) {s[j] += cnt[i];}}for (int i = 0; i < n; ++i) printf("%d\n", s[a[i]] - 1);return 0;
}

题目2：1294樱花

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1e6 + 10, mod = 1e9 + 7;int primes[N], cnt;
bool st[N];void init(int n) {for (int i = 2; i <= n; ++i) {if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] * i <= n; ++j) {st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}int main() {int n;cin >> n;init(n);int res = 1;for (int i = 0; i < cnt; ++i) {int p = primes[i];int s = 0;for (int j = n; j; j /= p) s += j / p;res = (LL)res * (2 * s + 1) % mod;}cout << res << endl;return 0;
}

题目3：198反素数

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;int primes[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int maxd, number;
int n;void dfs(int u, int last, int p, int s) {if (s > maxd || s == maxd && p < number) {maxd = s;number = p;}if (u == 9) return;for (int i = 1; i <= last; i++) {if ((LL)p * primes[u] > n) break;p *= primes[u];dfs(u + 1, i, p, s * (i + 1));}
}int main() {cin >> n;dfs(0, 30, 1, 1);cout << number << endl;return 0;
}

题目4：200Hankson的趣味题

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 50010;int primes[N], cnt;
bool st[N];
struct Factor {int p, s;
}factor[10];int fcnt;int dividor[1601], dcnt;void init(int n) {for (int i = 2; i <= n; ++i) {if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] * i <= n; ++j) {st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}void dfs(int u, int p) {if (u == fcnt) {dividor[dcnt++] = p;return;}for (int i = 0; i <= factor[u].s; ++i) {dfs(u + 1, p);p *= factor[u].p;}
}int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}int main() {init(N - 1);int n;cin >> n;while (n--) {int a, b, c, d;cin >> a >> b >> c >> d;fcnt = 0;int t = d;for (int i = 0; primes[i] <= t / primes[i]; ++i) {int p = primes[i];if (t % p == 0) {int s = 0;while (t % p == 0) t /= p, s++;factor[fcnt++] = {p, s};}}if (t > 1) factor[fcnt++] = {t, 1};dcnt = 0;dfs(0, 1);int res = 0;for (int i = 0; i < dcnt; ++i) {int x = dividor[i];if (gcd(a, x) == b && (LL)c * x / gcd(c, x) == d) res++;}cout << res << endl;}return 0;
}

题目5：201可见的点

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1010;int primes[N], cnt;
int euler[N];
bool st[N];void init() {int n = 1000;euler[1] = 1;for (int i = 2; i <= n; ++i) {if (!st[i]) {primes[cnt++] = i;euler[i] = i - 1;}for (int j = 0; primes[j] <= n / i; j++) {int t = primes[j] * i;st[t] = true;if (i % primes[j] == 0) {euler[t] = euler[i] * primes[j];break;}euler[t] = euler[i] * (primes[j] - 1);}}
}int main() {init();// for (int i = 1; i <= 50; ++i) {//     cout << "i = " << i << ", euler[i] = " << euler[i] << endl;// }int T;cin >> T;for (int tcase = 1; tcase <= T; tcase++) {int n;cin >> n;long long res = 0;for (int i = 1; i <= n; ++i) {//[1,i]中与i互质的整数的个数为euler[i]long long cnt = euler[i];res += cnt;}res *= 2;res += 1;cout << tcase << " " << n << " " << res << endl;}return 0;
}

题目6：220最大公约数

C++代码如下，

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1e7 + 10;int primes[N], cnt;
bool st[N];
int phi[N];
LL s[N];void init(int n) {for (int i = 2; i <= n; ++i) {if (!st[i]) {primes[cnt++] = i;phi[i] = i - 1;}for (int j = 0; primes[j] * i <= n; ++j) {st[primes[j] * i] = true;if (i % primes[j] == 0) {phi[i * primes[j]] = phi[i] * primes[j];break;}phi[i * primes[j]] = phi[i] * (primes[j] - 1);}}for (int i = 1; i <= n; ++i) s[i] = s[i-1] + phi[i];
}int main() {int n;cin >> n;init(n);LL res = 0;for (int i = 0; i < cnt; ++i) {int p = primes[i];res += s[n / p] * 2 + 1;}cout << res << endl;return 0;
}