寒假刷题记录

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

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

 

#include <bits/stdc++.h>

#define fi first
#define se second
#define endl '\n'
#define pb push_back

using 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_back

using 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_back

using 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;
}

原文地址：https://blog.csdn.net/its_a_win/article/details/145305550

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！