Educational Codeforces Round 13

https://codeforces.com/contest/678
4/6：ABCD （1h）
前4题都很简单，E应该是个撞鸭dp但是我想不出来

A. Johny Likes Numbers

#include <bits/stdc++.h>

using namespace std;

int main () {
    int n, k;
    cin >> n >> k;
    int cnt = (n + k - 1) / k * k;
    if (n % k == 0) cnt += k;
    cout << cnt;
}

B. The Same Calendar

累加天数和，余数与当年相同且同为/同不为闰年即可。

#include <bits/stdc++.h>

using namespace std;
int n, sum;

bool isLeap (int x) {
    if (x % 400 == 0)       return  true;
    if (x % 4 == 0 && x % 100)  return true;
    return false;
}

int main () {
    cin >> n;
    if (isLeap (n)) {
        sum += 366;
        for (int i = n + 1; ; i ++) {
            int dx = isLeap (i);
            sum += 365 + dx;
            //cout << i << ' ' << dx << ' ' << sum << ' ' << sum % 7 << endl;
            if (dx && sum % 7 == 2) {
                cout << i;
                break;
            }
        }
    }
    else {
        sum += 365;
        for (int i = n + 1; ; i++) {
            int dx = isLeap (i);
            sum += 365 + dx;
            //cout << i << ' ' << dx << ' ' << sum << ' ' << sum % 7 << endl;
            if (!dx && sum % 7 == 1) {
                cout << i;
                break;
            }
        }
    }
}

C. Joty and Chocolate

数学+简单容斥

#include <bits/stdc++.h>
#define int long long

using namespace std;
int n, a, b, p, q, cnta, cntb, cntab;

signed main () {
    cin >> n >> a >> b >> p >> q;
    cnta = n / a - (1 + a - 1) / a + 1;
    cntb = n / b - (1 + b - 1) / b + 1;
    int ab = (a * b) / __gcd (a, b);
    cntab = n / ab - (1 + ab - 1) / ab + 1;
    //cout << cnta << ' ' << cntb << ' ' << cntab << endl;
    cout << (cnta - cntab) * p + (cntb - cntab) * q + cntab * max (p, q);
}

//1-n里面有多少个x的倍数

D. Iterated Linear Function

复合函数推是式子：

除法那里要用逆元+注意特判 \(A=1\)

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int p = 1e9 + 7;
int a, b, n, x;

int qmi(int a, int k) {
	int ans = 1;
	while (k) {
		if (k & 1)	ans = ans * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return ans;
}

signed main () {
    cin >> a >> b >> n >> x;
    if (a == 1) {
        cout << (x + n % p * a % p * b % p) % p;
        return 0;
    }
    int da = qmi (a, n), inv = qmi (a - 1, p - 2);
    //cout << da;
    cout << (x % p * da + (da - 1) * inv % p * b) % p;
}

//A^n * x + (1-A^n)/(1-A) * B

E. Another Sith Tournament

EF待补

F. Lena and Queries