A-C(暂时) 在补了在补了
A. Orac and Factors
函数 f(x) 为x约数中大于1的最小的数,每一次操作使 n=n+f(n),求k此操作后的n。
不难理解:f(n+f(n))=2,因为偶数约数一定有2,奇数的约数一定为奇数,
然后对于n为奇数,找一次f(n),剩下操作的一直加2。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) ll n, k; int vis[1000010]; ll prime[1000010], id = 0; void solve() { cin >> n >> k; if (n & 1) { rep(i, 1, n) if (n % prime[i] == 0) { cout << n + prime[i] + 2 * (k - 1) << endl; break; } } else cout << n + k * 2 << endl; } int main() { rep(i, 2, 1000010) { if (!vis[i]) prime[++id] = i; for (int j = 1; j <= id && i * prime[j] <= 1000000; j++) vis[i * prime[j]] = 1; } int t; cin >> t; while (t--) { solve(); } }
B. Orac and Models
求上升子序列,且满足相邻两项在原序列中的下标能被整除。
跟传统的上升子序列差不多。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) ll n, k; ll s[100010], dp[100010], ans; void solve() { cin >> n; ans = 1; rep(i, 1, n) { cin >> s[i]; dp[i] = 1; } rep(i, 1, n) { ans = max(ans, dp[i]); for (int j = i * 2; j <= n; j += i) if (s[i] < s[j]) dp[j] = max(dp[j], dp[i] + 1); } cout << ans << endl; } int main() { int t; cin >> t; while (t--) { solve(); } }
C. Orac and LCM
题意是s数组,求gcd({lcm({ai,aj},i<j)})
将ai分解质因子p1ki1,p2ki2,,,
lcm(ai,aj)即为 p1max(ki1,kj1) * p2max(ki2,kj2) *...
gcd(ai,aj)即为 p1min(ki1,kj1) * p2min(ki2,kj2) *...
结合起来就是求pxmin(max(kix,kjx))
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) ll ksm(ll a, ll b) { ll res = 1; for (; b; b >>= 1, a *= a) if (b & 1) res *= a; return res; } ll n, a[100010]; ll ans = 1; int vis[1000010]; ll prime[1000010], id = 0; void solve() { cin >> n; rep(i, 1, n) cin >> a[i]; for (int j = 1; j <= id; j++) { int m1 = 1000000, m2 = 1000000; for (int i = 1; i <= n; i++) { int tmp = 0; while (a[i] % prime[j] == 0) { tmp++; a[i] /= prime[j]; } if (tmp < m1) swap(tmp, m1); if (tmp < m2) swap(tmp, m2); if (m2 == 0) break; } ans *= ksm(prime[j], m2); } cout << ans << endl; } int main() { rep(i, 2, 200010) { if (!vis[i]) prime[++id] = i; for (int j = 1; j <= id && i * prime[j] <= 200010; j++) vis[i * prime[j]] = 1; } int t; t = 1; while (t--) { solve(); } }