题目A. Bob 的私房钱
知识点：
分解质因数
思路：
又是分解质因数(●—●)，最后公式确实退不出来，还是直接附上题解吧
代码：
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' int t; vector<int> v; map<int, int> vis; void fenjie(int x) { for (int i = 2; i * i <= x; i++) { if (x % i == 0) { x /= i; if (!vis[i]) v.push_back(i); vis[i]++; i--; } } if (x > 1) { if (!vis[x]) v.push_back(x); vis[x]++; } return; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> t; while (t--) { v.clear(); vis.clear(); int n; cin >> n; fenjie(n + 1); int ans = 0; for (int i = 1; i <= v.size() ; i++) { ans += (v[i - 1] - 1) * vis[v[i - 1]]; } cout << ans << endl; } return 0; }题目E. 小清新数论题
知识点：
lcm，线性筛，快速幂
关键：
依旧数论，依旧卡死
思路：
找到每个质数p对应最大的k，使得p的k次方小于等于n，最后累乘起来就可以，该题线性筛的复杂度就够，难点还是在分解质因数
代码：
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int N = 3e5+10; int n, p; int check(int x) { for (int i = 2; i <= sqrt(x); i++) { if (x % i == 0) return 0; } return 1; } int ksm(int x, int y) { int a = x; int ANS = 1; while (y) { if (y & 1) ANS = ANS * a; a = a * a; y >>= 1; } return ANS; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> p; int ans = 1; for (int i = 2; i <= n; i++) { if (check(i)) { int k = 1; while (ksm(i, k) <= n) k++; ans = (ans * ksm(i, k - 1)) % p; } } cout << ans << endl; return 0; }
