A - Mischievous Problem Setter

签到题，排序，然后扫一遍累加时间，直到时间到了限制为止。代码如下

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
// #define endl "\n"
// const int MAXN = ;
// const int MAXE = ;
// const int MOD = ;
// const int INF = ;
// const double eps = ;
// const double PI = acos(-1);
// const int DIRX[] = {};
// const int DIRY[] = {};
const int MAXN = 1e5+100;
int t,n,m;
struct P{
    int d,t;
}a[MAXN];
bool cmp(P x, P y){
    if(x.d == y.d){
        return x.t < y.t;
    }
    return x.d < y.d;
}
signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> t;
    int _ = 0;
    while(t--){
        _++;
        cin >> n >> m;
        for(int i=1;i<=n;i++){
            cin >> a[i].d;
        }
        for(int i=1;i<=n;i++){
            cin >> a[i].t;
        }
        sort(a+1,a+1+n,cmp);
        int ans = 0;
        int tt = 0;
        for(int i=1;i<=n;i++){
            if(tt + a[i].t <= m){
                ans++;
                tt+=a[i].t;
            }else{
                break;
            }
        }
        //Case 1: 3
        cout << "Case " << _ << ": " << ans << endl;
    }
    return 0;
}

K - Mr. Panda and Kakin

题意略。
做出如下替换


根据欧拉函数可以得到下面两个方程


做出如下替换
令


根据欧拉函数可知

所以

由题目给出条件 以及欧拉函数可得

可得

可得

逆元通过 或者费马小定理求逆元得即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long n, c, phin;
long long qMul(long long a, long long b, long long c) {
    return (a * b - (long long)floor( (long double)a * (long double)b / (long double)c + 0.5 ) * c + c) % c;
}
int qPow(int a, int b, int p) {
    int ans = 1;
    for (; b; b >>= 1, a = qMul(a, a, p))
        if (b & 1) ans = qMul(ans, a, p);
    return ans;
}
int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int inv(int a, int p) {
    int x, y;
    int d = exgcd(a, p, x, y);
    return d == 1 ? (x % p + p) % p : -1;
}
signed main(void)
{
    int T, cas = 0;
    cin >> T;
    long long zz = (1 << 30) + 3;
    while (T--)
    {
        cas++;
        scanf("%lld%lld", &n, &c);
        printf("Case %d: ", cas);
        long long x = sqrt(n);
        long long p = x, q = x;
        while(n % p) p--;
        q = n / p;
        phin = (p-1) * (q-1);
        long long xx, yy;
        xx = inv(zz,phin);
        long long ans = qPow(c, xx, n);
        printf("%lld\n",ans);
    }
    return 0;
}