k-rounding

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

LL lcm(LL a, LL b) {
    LL MAX = max(a, b), MIN = min(a, b);

    for (int i = 1;; i ++ )

        if (!(i * MAX % MIN))
            return i * MAX;
}

int main() {
    LL n, k;
    cin >> n >> k;
    LL m = pow(10, k);
    cout << lcm(n, m) << endl;
    return 0;
}

美素数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int a[N], cnt;
bool st[N];

int f(int x) {
    int res = 0;

    while (x) {
        res += x % 10;
        x /= 10;
    }

    return res;
}

void get_primes() {

    for (int i = 2; i < N; i ++ ) {

        if (st[i])
            continue;

        for (int j = i + i; j < N; j += i )

            st[j] = true;
    }
}

int main() {
    get_primes();

    for (int i = 2; i < N; i ++ ) {

        if (!st[i] && !st[f(i)])
            cnt ++ ;
        a[i] = cnt;
    }

    int l, r;
    int t, casei = 0;
    cin >> t;

    while (t -- ) {
        scanf("%d%d", &l, &r);
        printf("Case #%d: %d\n", ++ casei, a[r] - a[l - 1]);
    }

    return 0;
}

青蛙的约会

#include <iostream>

using namespace std;

typedef long long LL;

int exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return d;
}

int main() {
    LL x, y, m, n, l;
    cin >> x >> y >> m >> n >> l;

    LL _x, _y;
    LL A = n - m, M = x - y;

    if (A < 0) {
        A = -A;
        M = -M;
    }

    int d = exgcd(A, l, _x, _y);
    int r = l / d;

    if (M % d)
        cout << "Impossible" << endl;
    else
        cout << ((_x * M / d) % r + r) % r << endl;

    return 0;
}

Sum

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int mo = 1e9 + 7;

const int N = 100010;

typedef long long LL;

char a[N];

int qmi(int a, int k, int p) {
    LL res = 1 % p;

    while (k) {
        if (k & 1)
            res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }

    return res;
}

int main() {
    while (~scanf("%s", a)) {
        int l = strlen(a);
        LL k = 0;

        for (int i = 0; i < l; i ++ )

            k = (k * 10 + a[i] - '0') % (mo - 1);
        k = (k - 1 + mo - 1) % (mo - 1);
        printf("%d\n", qmi(2, k, mo));
    }

    return 0;
}

Prime Distance

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define INF 0x3f3f3f3f

const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void get_primes() {
    for (int i = 2; i < N; i ++ ) {

        if (st[i])
            continue;
        primes[cnt ++ ] = i;

        for (int j = i + i; j < N; j += i)

            st[j] = true;
    }
}

int main() {
    get_primes();
    int l, u;

    while (cin >> l >> u) {
        memset(st, false, sizeof st);

        for (int i = 0; i < cnt; i ++ ) {

            int a = l / primes[i];
            int b = u / primes[i];

            for (int j = max(a, 2); j <= b; j ++ )

                st[j * primes[i] - l] = true;
        }

        if (l == 1)
            st[0] = true;
        int max = -INF, min = INF;
        int minl, minr, maxl, maxr;
        int mark = -1;

        for (int i = 0; i <= u - l; i ++ ) {

            if (st[i])
                continue;

            if (mark == -1) {
                mark = i;
                continue;
            }

            if (i - mark > max) {
                max = i - mark;
                maxl = mark;
                maxr = i;
            }

            if (i - mark < min) {
                min = i - mark;
                minl = mark;
                minr = i;
            }

            mark = i;
        }

        if (min == INF || max == -INF)
            cout << "There are no adjacent primes." << endl;
        else
            printf("%d,%d are closest, %d,%d are most distant.\n", minl + l, minr + l, maxl + l, maxr + l);
    }

    return 0;
}