2025-11-06

CF补题

Problem - 515C - Codeforces（1400）（string+a little factorial）

这题妙在把各个数字阶乘转换成仅含有2 3 5 7 数字，然后直接求解
要对每个数的阶乘进行换算

[!tip]

   9 is 7!*8*9=7!*3!*3!*2!8 is 7!*8=7!*2!*2!*2!7 is 7!6 is 5!*6=5!*3!5 is 5!4 is 3!*4=3!*2!*2!3 is 3!=62 is 2!=2

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;vector<string> vs = {"", "", "2", "3", "322", "5", "53", "7", "7222", "7332"};//更换数字，很妙string res;char ch;for (int i = 0; i < n;i++){cin >> ch;res+=vs[ch-'0'];}sort(res.begin(), res.end(), greater<char>());//从大到小排序cout << res << endl;
}

Problem - 548B - Codeforces（水题）

要学会看数据范围！！计算时间复杂度，能做的直接暴力

数论

Problem - 632D - Codeforces(LCM)(2100)

这题难点在

• 从lcm考虑能选因数最大值(1e6)
• 用调和级数计算时间复杂度
  （m+m/2+m/3……+m/m）=logm

P2158 [SDOI2008] 仪仗队 - 洛谷(欧拉函数)

人被挡住，当且仅当gcd(x,y)!=1，这样会被（x/gcd,y/gcd）的人挡住
所以该题要求的是数互质的数量->欧拉函数
时间复杂度小的话用不需要用线性筛

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=4e4+10;
int e[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, ans = 2;cin >> n;if(n==1){cout << 0 << endl;return 0;}//欧拉函数埃式筛求法 O(loglogn)for (int i = 1; i <= n;i++){e[i] = i;}for (int i = 2; i <= n;i++){if(e[i]==i){for (int j = i; j <= n;j+=i){e[j] = e[j] / i * (i - 1);}}}for (int i = 2; i <= n - 1;i++){ans += e[i]*2;//对称}ans++;//(1,1)cout << ans << endl;
}