D - Factorial and Multiple
前置知识
\(n!\)中包含素因子\(p\)的个数为
\[ cnt = \sum\limits_{k \geq 1}^{p^k \leq n} \lfloor \frac{n}{p^k} \rfloor \]例如:\(n!\)中包含的2的个数可以这么找:先找1~n中2的倍数的个数\(\lfloor \frac{n}{2} \rfloor\),再找1~n中4的倍数的个数\(\lfloor \frac{n}{4} \rfloor\),再......直到\(2^k > n\)为止。
思路
先对k进行质因数分解,再二分\(n\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {
#ifdef LOCAL
freopen("in.in", "r", stdin);
#endif
_A_A_();
_u_u_;
return 0;
}
#define int long long
const int mod = 1e9 + 7;
const int maxn = 1e12 + 10;
const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) {
res = res * a;
}
a = a * a;
b >>=1;
}
return res;
}
vector<pair<int,int>> p;
bool check(int mid ) {
for (auto x : p) {
int temp = 0;
for (int i = 1;qpow(x.first,i) <= mid;i++) {
temp += mid / qpow(x.first, i);
}
if (temp < x.second) return 0;
}
return 1;
}
inline void _A_A_() {
int k,t;
cin >> k;
t = k;
for (int i = 2;i <= sqrt(k);i++) {
if (t % i == 0) {
p.push_back({i,0});
}
while (t % i == 0) {
p.back().second++;
t /= i;
}
}
if (t != 1) {
p.push_back({t,1});
}
int l = 1, r = maxn;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) {
r = mid;
}
else {
l = mid + 1;
}
}
cout << l << "\n";
}
E - Critical Hit
状态表示
\(dp[i]\)表示当将怪物打到还剩\(i\)生命值时攻击的期望次数。
转移方程
\[ dp[i] = (\frac{p}{100} * dp[i + 2] + (1 - \frac{p}{100}) * dp[i + 1] + 1) \bmod mod \]编码的两种方法
- 一
这里将100
在模mod下的逆元inv
先求了出来,这样1-p/100
就能表示为(100-p) * inv
,p/100
就能表示为p * inv
。
但是,无法得到正确答案。
inline void _A_A_() {
int n, p;
cin >> n >> p;
int inv = qpow(100, mod - 2);
dp[n] = 0;
for (int i = n - 1;i >= 0;i -- ) {
dp[i] = (p * inv * dp[i + 2] % mod + (100 - p) * inv * dp[i + 1] % mod + 1 + mod) % mod;
}
cout << dp[0] << "\n";
}
- 二
这里m
表示p/100
在模mod下的表示。这样1 - p/100
就能表示为1 - m
。
这样答案正确!!!
inline void _A_A_() {
int n, p;
cin >> n >> p;
int m = p * qpow(100, mod - 2) % mod;
dp[n] = 0;
for (int i = n - 1;i >= 0;i -- ) {
dp[i] = (dp[i + 1] * (1 - m + mod) % mod + dp[i + 2] * m % mod + 1) % mod;
}
cout << dp[0] << "\n";
}
标签:AtCoder,frac,Beginner,int,inv,280,100,dp,mod
From: https://www.cnblogs.com/FanWQ/p/16948938.html