D - AABCC (atcoder.jp)
（1）题目大意
给你个数N，问你不超过N的三个质数abc组成的数有多少个。
（2）解题思路
考虑到枚举的数不会特别多，因此预处理出1e6的质因子，暴力枚举即可。
（3）代码实现文章来源地址https://www.toymoban.com/news/detail-431115.html
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
struct Primes {
bitset <N> st;
int cnt,primes[N],idx[N],n;
Primes(int n = N - 1) {
this->n = n;
init(n);
}
void init(int n) {
st[0] = st[1] = 1;
for(int i = 2;i <= n;i ++) {
if(!st[i]) {
primes[++ cnt] = i;
idx[i] = cnt;
}
for(int j = 1;primes[j] <= n / i;j ++) {
st.flip(primes[j] * i);
if(i % primes[j] == 0) break;
}
}
}
//判断x是否是质数
bool isPrime(int x) {
assert(x <= n);
return !st[x];
}
//求解x在质数表是第几个
bool atIndex(int x) {
assert(!st[x]);
assert(x <= n);
return idx[x];
}
};
using i128 = __int128;
void solve(){
ll n;
cin >> n;
Primes pr(1e6);
vector <int> v;
for(int i = 1;i <= 1e6;i ++) {
if(pr.isPrime(i)) v.pb(i);
}
int cnt = 0,siz = sz(v);
for(int i = 0;i < siz;i ++) {
ll v1 = 1ll * v[i] * v[i];
if(v1 > n) break;
for(int j = i + 1;j < siz;j ++) {
i128 v2 = (i128) 1 * v[j];
if((i128) 1ll * v1 * v2 > n) break;
for(int k = j + 1;k < siz;k ++) {
i128 v3 = 1ll * v[k] * v[k];
if((i128) v1 * v2 * v3 > n) break;
cnt ++;
}
}
}
cout << cnt << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
// cin >> T;
while(T --) solve();
}E - Dice Product 3 (atcoder.jp)
（1）题目大意
给你一个数N，然后给你一个初始数1，每次你可以摇一下骰子，摇到多少把当前的数乘上多少，问你最后变成N的概率是多少？
（2）解题思路
观察题目，考虑1没用，我们可以直接dp[i][j][k]表示2还剩i次，3还剩j次，5还剩k次的概率，因为4和6可以用2和3表示出来，因此我们考虑把N质因子分解，然后倒着dp即可。
需要注意的是每一次只需要乘上1/5的概率。
解释：考虑当前数为n
移项可得
（3）代码实现
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define PII pair<int,int>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define gc getchar
#define pc putchar
using namespace std;
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
const ll mod = 998244353;
ll ksm(ll a,ll b)
{
ll res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
template <class T = int> T read() {
T x = 0; bool f = 0; char ch = gc();
while (!isdigit(ch)) f = ch == '-', ch = gc();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc();
return f ? -x: x;
}
template <class T> void write(T x) {
if (x >= 0) { if (x > 9) write(x / 10); pc(x % 10 + 48); }
else { pc('-'); if (x < -9) write(-x / 10); pc(48 - x % 10); }
}
namespace pr {
mt19937_64 rnd(random_device{}());
using ull = unsigned long long;
using u128 = unsigned __int128;
struct barrett_64 {
ull mod, r;
u128 k;
barrett_64(ull _mod) {
mod = _mod;
r = __lg(mod);
if ((1ull << r) < mod) r++;
k = ((r == 64 ? u128(0) : u128(1) << r * 2) - 1) / mod + 1;
}
ull mul(ull a, ull b) {
u128 c = ((u128(a) * b >> r) * k) >> r;
if (c) c--;
u128 d = u128(a) * b - u128(c) * mod;
while (d >= mod) d -= mod;
return d;
}
ull sub(ull a, ull b) { return a < b ? a - b + mod : a - b; }
ull add(ull a, ull b) { return sub(a, mod - b); }
} reducer(1);
ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull qpow(ull a, ull b) {
ull res(1);
for (; b; b >>= 1, a = reducer.mul(a, a))
if (b & 1) res = reducer.mul(res, a);
return res;
}
bool is_prime(ull n) {
if (n <= 1) return false;
vector<ull> base = {2, 3, 5, 7, 11, 13, 17, 19, 23};
for (ull p : base) {
if (n == p) return true;
if (n % p == 0) return false;
}
reducer = barrett_64(n);
ull m = (n - 1) >> __builtin_ctz(n - 1);
for (ull p : base) {
ull t = m, a = qpow(p, m);
while (t != n - 1 && a != 1 && a != n - 1)
a = reducer.mul(a, a), t *= 2;
if (a != n - 1 && t % 2 == 0) return false;
}
return true;
}
ull get_factor(ull n) {
if (n % 2 == 0) return 2;
reducer = barrett_64(n);
auto f = [&](ull x) { return reducer.add(reducer.mul(x, x), 1); };
ull x = 0, y = 0, tot = 0, p = 1, q, g;
for (ull i = 0; (i & 0xff) || (g = gcd(p, n)) == 1; i++) {
if (x == y) {
x = tot, y = f(x);
if (++tot == n) tot = 0;
}
q = reducer.mul(p, reducer.sub(x, y));
if (q) p = q;
x = f(x), y = f(f(y));
}
return g;
}
vector<ull> solve(ull n) {
if (n == 1) return {};
if (is_prime(n)) return {n};
ull d = get_factor(n);
auto v1 = solve(d), v2 = solve(n / d);
auto i1 = v1.begin(), i2 = v2.begin();
vector<ull> ans;
while (i1 != v1.end() || i2 != v2.end()) {
if (i1 == v1.end()) ans.push_back(*i2++);
else if (i2 == v2.end()) ans.push_back(*i1++);
else {
if (*i1 < *i2) ans.push_back(*i1++);
else ans.push_back(*i2++);
}
}
return ans;
}
}
using i64 = long long;
constexpr int P = 998244353;
// assume -P <= x < 2P
int Vnorm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Mint {
int x;
Mint(int x = 0) : x(Vnorm(x)) {}
Mint(i64 x) : x(Vnorm(x % P)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(Vnorm(P - x));
}
Mint inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Mint &operator*=(const Mint &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = Vnorm(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = Vnorm(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, Mint &a) {
i64 v;
is >> v;
a = Mint(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Mint &a) {
return os << a.val();
}
};
Mint dp[63][63][63];
int have[4];
void solve(){
ll n;
cin >> n;
auto f = pr::solve(n);
if(f.back() >= 7) {
cout << 0 << endl;
return;
}
for(auto x : f) {
if(x == 2) have[1] ++;
if(x == 3) have[2] ++;
if(x == 5) have[3] ++;
}
dp[have[1]][have[2]][have[3]] = 1;
ll tv = ksm(5,P - 2);
int a = have[1],b = have[2],c = have[3];
for(int i = a;i >= 0;i --) {
for(int j = b;j >= 0;j --) {
for(int k = c;k >= 0;k --) {
if(i == a && j == b && k == c) continue;
if(i + 1 <= a) dp[i][j][k] += dp[i + 1][j][k];
if(j + 1 <= b) dp[i][j][k] += dp[i][j + 1][k];
if(k + 1 <= c) dp[i][j][k] += dp[i][j][k + 1];
if(i + 2 <= a) dp[i][j][k] += dp[i + 2][j][k];
if(i + 1 <= a && j + 1 <= b) dp[i][j][k] += dp[i + 1][j + 1][k];
dp[i][j][k] *= tv;
}
}
}
cout << dp[0][0][0] << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
// cin >> T;
while(T --) solve();
}F - More Holidays (atcoder.jp)
（1）题目大意
给你一次长度为N的字符串S，然后复制了M遍，问你可以一定把K个x变成o，问你最大的连续o的长度为多少？ 
（2）解题思路
考虑前缀和预处理出每一个x的位置，然后枚举在这些x的位置开始改k次，O1即可算出来改了K个之后的位置，以及答案是多少。
（3）代码实现
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
void solve(){
ll n,m,k;
string s;
cin >> n >> m >> k;
cin >> s;
vector<int> p;
for(int i = 0;i < n;i ++) {
if(s[i] == 'x') p.pb(i);
}
auto get = [&](ll k) {
ll rp = p[k % sz(p)] + k / sz(p) * n;
return min(rp,n * m);
};
ll ans = get(k);
for(int i = 0;i < sz(p);i ++) ans = max(ans,get(i + k + 1) - p[i] - 1);
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
// cin >> T;
while(T --) solve();
}G - P-smooth number (atcoder.jp)
（1）题目大意
（2）解题思路
用两个数组存下来前半部分的素数乘和后半部分的素数乘出来的数，然后排个序，枚举第一个数组，然后第二个数组用双指针扫一下计算贡献即可。文章来源：https://www.toymoban.com/news/detail-431115.html
（3）代码实现
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
struct Primes {
bitset <N> st;
int cnt,primes[N],idx[N],n;
Primes(int n = N - 1) {
this->n = n;
init(n);
}
void init(int n) {
st[0] = st[1] = 1;
for(int i = 2;i <= n;i ++) {
if(!st[i]) {
primes[++ cnt] = i;
idx[i] = cnt;
}
for(int j = 1;primes[j] <= n / i;j ++) {
st.flip(primes[j] * i);
if(i % primes[j] == 0) break;
}
}
}
//判断x是否是质数
bool isPrime(int x) {
assert(x <= n);
return !st[x];
}
//求解x在质数表是第几个
bool atIndex(int x) {
assert(!st[x]);
assert(x <= n);
return idx[x];
}
}pr(100);
ll n,p;
void dfs(vector<ll> &a,int z)
{
for(int i = 0;i < sz(a);i ++) {
if(a[i] * z < n) {
a.pb(a[i] * z);
}
}
}
void solve(){
cin >> n >> p;
vector<int> f;
for(int i = 1;i <= p;i ++) {
if(pr.isPrime(i)) f.pb(i);
}
vector<ll> v1,v2;
v1.pb(1),v2.pb(1);
for(int i = 0;i < sz(f);i ++) {
if(sz(v1) < sz(v2)) dfs(v1,f[i]);
else dfs(v2,f[i]);
}
sort(all(v1));
sort(all(v2));
int j = sz(v2) - 1;
ll ans = 0;
for(int i = 0;i < sz(v1);i ++) {
ll pv = n / v1[i];
while(j >= 0 && v2[j] > pv) j --;
ans += j + 1;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1;
// cin >> T;
while(T --) solve();
}到了这里，关于AtCoder Beginner Contest 300（D-G）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
