对n分解质因数，设某个质因数出现的次数为cnt。每个质因数每次取得越少越好，即构成自然数列1+2+...+n，我们要找的就是最大的n使得$1+2+...+n \leq cnt$，这可以二分做。
复杂度$O(\frac{\sqrt{N}}{\log{\sqrt{N}}})$。
#include <iostream> #include <cstdio> using namespace std; typedef long long ll; ll n, ans; ll f[51]; int prime[1000010], mark[1000010], tot; ll find(ll x) { ll l = 1, r = 1000000, ret = -1; while (l <= r) { ll mid = (l + r) >> 1; if (mid * (mid + 1) / 2 <= x) { ret = mid; l = mid + 1; } else { r = mid - 1; } } return ret; } void get_prime() { for (int i = 2; i <= 1000000; i++) { if (!mark[i]) prime[++tot] = i; for (int j = 1; j <= tot; j++) { if (prime[j] * i > 1000000) break; mark[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } } int main() { get_prime(); for (int i = 1; i <= 50; i++) { f[i] = find(i); } cin >> n; for (int i = 1; prime[i] * prime[i] <= n && i <= tot; i++) { if (n % prime[i] == 0) { ll cnt = 0; while (n % prime[i] == 0) { cnt++; n /= prime[i]; } ans += f[cnt]; } } if (n > 1) { ans++; } cout << ans; return 0; }
结论题，不会证，感性理解吧QWQ。
#include <iostream> #include <cstdio> #include <algorithm> #include <map> using namespace std; long long a[200010], b[200010]; int n; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); if (n % 2) { cout << b[n / 2 + 1] - a[n / 2 + 1] + 1; } else { cout << b[n / 2] + b[n / 2 + 1] - a[n / 2] - a[n / 2 + 1] + 1; } return 0; }
这算是一道非常明显的背包题。
我们可以考虑算出所有可以凑数s的集合，然后再看看它属于多少个集合。
设$f[i][j]$代表选$i$个数，和为$j$的方案数，则答案为$\sum_{i=1}^{n}f[i][s] \times 2^{n-i}$。
有转移方程：$f[i][j]+=f[i-1][j-a[i]]$
但是这么dp的复杂度为$O(N^2 \times S)$，显然爆炸，考虑优化。
考虑最后答案的式子，设$g[j]=\sum_{i=1}^{n}f[i][j] \times 2^{n-i}$。
我们再来看看f的转移方程，我们发现有$g[j]+=g[j-a[i]]/2$，然后这道题就做完了。
#include <iostream> #include <cstdio> using namespace std; typedef long long ll; const ll MOD = 998244353; ll n, s; ll a[3010]; ll f[3010]; ll inv2; ll ksm(ll aa, ll b) { ll ret = 1; while (b) { if (b & 1) ret = (ret * aa) % MOD; aa = (aa * aa) % MOD; b >>= 1; } return ret; } int main() { cin >> n >> s; for (ll i = 1; i <= n; i++) cin >> a[i]; inv2 = ksm(2, MOD - 2); f[0] = ksm(2, n); for (ll i = 1; i <= n; i++) { for (ll k = s; k >= a[i]; k--) { f[k] = (f[k] + f[k - a[i]] * inv2) % MOD;//除以2等于乘以2的逆元 } } cout << f[s]; return 0; }
AtCoder Beginner Contest 169部分题解（ATcoder）
原文：https://www.cnblogs.com/zcr-blog/p/13021952.html