期末周没啥时间，刷点水题
CF
Problem - 271B - Codeforces（1300）（暴力枚举）
多练多练呀
突然发现欧拉筛的板子有一点点问题，没有考虑到1不是质数的情况
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N = 1e6 + 10;
bool st[N];
int prime[N];
int cnt;
int r[N], c[N];void get_prime(int n)
{st[1] = true;//补充for (int i = 2; i <= n;i++){if(!st[i])prime[cnt++] = i;for (int j = 0; prime[j] <= n / i;j++){st[prime[j] * i] = true;if(i%prime[j]==0)break;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);get_prime(2e5 + 10);int n,m;cin >> n>>m;for (int i = 0; i < n;i++){for (int j = 0,x; j < m;j++){cin >> x;int cnt = 0;while(st[x])cnt++, x++;r[i] += cnt;c[j] += cnt;}}int ans = 1e9;for (int i = 0; i<n;i++)ans = min(ans, r[i]);for (int i = 0; i < m;i++)ans = min(ans, c[i]);cout << ans << endl;
}
Problem - 1823C - Codeforces（质因数）（1300）
这个要讨论强合数的情况
- 两个相同质数乘积
- 三个不同质数乘积
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
map<int, int> mp;
void sol(int x){for (int i = 2; i * i <= x;i++){if(x%i==0){while(x%i==0)mp[i]++,x/=i;//计数}}if(x>1)mp[x]++;
}void solve()
{int n;cin >> n;mp.clear();for (int i = 0, x; i < n;i++){cin >> x;sol(x);}int ans = 0, cnt = 0;for(auto x:mp){ans += x.second / 2;cnt += x.second % 2;}cout << ans + cnt / 3 << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}