4968. 互质数的个数 - AcWing题库

涉及：快速幂，欧拉函数，分解质因数

 

#include <bits/stdc++.h>		#define fi first
#define se second
#define endl '\n'
#define pb push_backusing namespace std;
using LL = long long;const int mod = 998244353;const int N = 1e5 + 10; LL a,b;LL mo(LL n)
{return (n % mod + mod) % mod;
}LL qmi(LL a,LL b)
{LL res = 1;while(b){if (b & 1) res = res * a % mod;a = a * a % mod,b >>= 1;}return res;
}LL eular(LL n)
{LL res = n;for (int i = 2;i <= n / i;i ++){if (n % i) continue;res = res / i * (i - 1);while(n % i == 0) n /= i;}if (n > 1) res = res / n * (n - 1);return res;
}void solve()
{cin >> a >> b;if (a == 1) cout << 0 << endl;else    cout << mo(eular(a) * qmi(a,b - 1)) << endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _ = 1;// cin >> _;while(_--) solve();return 0;
}	

5395. 平均 - AcWing题库 简单

贪心

#include <bits/stdc++.h>		#define fi first
#define se second
#define endl '\n'
#define pb push_backusing namespace std;
using LL = long long;
typedef pair<int,int> PII;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;const int mod = 998244353;const int N = 1e5 + 10; vector<LL> v[12];int n;bool cmp(const LL &a,const LL &b)
{return a > b;
}void solve()
{cin >> n;for (int i = 1;i <= n;i ++){LL a,b; cin >> a >> b;v[a].push_back(b);}for (int i = 0;i < 10;i ++) sort(v[i].begin(),v[i].end(),cmp);LL ans = 0;LL cnt = n / 10;for (int i = 0;i < 10;i ++){if (v[i].size() > cnt) for (int j = cnt;j < v[i].size();j ++) {ans += v[i][j];// cout << v[i][j] << "==" << endl;}}cout << ans << endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _ = 1;// cin >> _;while(_--) solve();return 0;
}	

4965. 三国游戏 - AcWing题库

贪心

 

 

#include <bits/stdc++.h>		#define fi first
#define se second
#define endl '\n'
#define pb push_backusing namespace std;
using LL = long long;
typedef pair<int,int> PII;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;const int mod = 998244353;const int N = 1e5 + 10; LL a[N],b[N],c[N],w[N];
int n;LL work(LL a[],LL b[],LL c[])//a是获胜国,其他是失败国
{LL res = -1;LL sum = 0;for (int i = 1;i <= n;i ++) w[i] = a[i] - b[i] - c[i];sort(w + 1,w + 1 + n,greater<LL>());//从大到小排序for (int i = 1;i <= n;i ++){sum += w[i];if (sum > 0) res = i;else break; }return res;}void solve()
{cin >> n;for (int i = 1;i <= n;i ++) cin >> a[i];for (int i = 1;i <= n;i ++) cin >> b[i];for (int i = 1;i <= n;i ++) cin >> c[i];cout << max({work(a,b,c),work(b,a,c),work(c,a,b)}) << endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _ = 1;// cin >> _;while(_--) solve();return 0;
}