読者です 読者をやめる 読者になる 読者になる

Educational Codeforces Round 13

http://codeforces.com/contest/678
 簡単に。
A
 要領が悪くて変なのを書いたらHackされた……

int main() {
    ll n, k; cin >> n >> k;
    cout << (n / k + 1) * k << endl;
    return 0;
}

B
 is_ururu。

bool is_leap(int y) {
    if(y % 4 != 0) return false;
    if(y % 100 == 0 && y % 400 != 0) return false;
    return true;
}
int main() {
    int y; cin >> y;
    ll sum = 0LL;
    bool yl = is_leap(y);
    for(int i = y + 1; ; ++i) {
        sum += is_leap(i) ? 366LL : 365LL;
        if(sum % 7 == 0 && yl == is_leap(i)){
            cout << i << endl;
            return 0;
        }
    }
}

C
これも要領が悪かった。最小公倍数はgcdを使うのが定石っぽいのですが要領が悪くわざわざ素因数分解しました。これもHackできそう。

map<ll, ll> prime_factor(ll n) {
    map<ll, ll> res;
    for(int i = 2; i * i <= n; ++i) {
        while(n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if(n != 1) res[n] = 1;
    return res;
}
int main() {
    ll n, a, b, p, q;
    cin >> n >> a >> b >> p >> q;
    map<ll, ll> pa = prime_factor(a);
    map<ll, ll> pb = prime_factor(b);
    ll koubai = 1LL;
    for(auto& k : pb)
      if(pa.count(k.first) == 0)
        rep(i, k.second) koubai *= k.first;
      else
        rep(i, max(k.second, pa[k.first])) koubai *= k.first;
    for(auto& k : pa)
      if(pb.count(k.first) == 0)
        rep(i, k.second) koubai *= k.first;
    ll rb = n / koubai;
    ll red = n / a - rb, blue = n / b - rb;
    ll ans = red * p + blue * q;
    if(p < q) ans += rb * q; else ans += rb * p;
    cout << ans << endl;
    return 0;
}

D
 色々解法はありそうですが行列累乗で解きました。Aとxを間違える謎バグを仕込んでおり大変でした。さすがにHackは大丈夫そう?

typedef vector<ll> vec; typedef vector<vec> mat;
const int MOD = 1000000007;
//A * B
mat mul(const mat& A, const mat& B) {
    mat C(A.size(), vec(B.size()));
    rep(i, A.size()) rep(k, B.size()) rep(j, B[0].size())
      C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}
//A ^ n
mat pow(mat A, ll n) {
    mat B(A.size(), vec(A.size()));
    rep(i, A.size()) B[i][i] = 1;
    while(n > 0) {
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1LL;
    }
    return B;
}

int main() {
    ll A, B, n, x;
    cin >> A >> B >> n >> x;
    mat prod(2, vec(2));
    prod[0][0] = A; prod[0][1] = B;
    prod[1][0] = 0; prod[1][1] = 1;
    mat a = pow(prod, n);
    ll ans = (a[0][0] * x) % MOD;
    ans = (ans + a[0][1] ) % MOD;
    cout << ans << endl;
    return 0;
}

 なんかこう、全体的に要領が悪すぎますね……。