「模拟测试」20171024

/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「SuperOJ 2007」建设图 24-10-2017
 * 缩点
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline bool read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return false;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig ? x = -x : 0;
    return true;
}

inline void read(char &c) {
    while (c = read(), isspace(c) && c != -1)
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void print(const char *s) {
    for (; *s; s++) print(*s);
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }

    ~InputOutputStream() { flush(); }
} io;
}

namespace {

const int MAXN = 100010;

std::vector<int> edge[MAXN + 1];

inline void addEdge(const int u, const int v) {
    edge[u].push_back(v), edge[v].push_back(u);
}

typedef std::vector<int>::iterator Iterator;

int low[MAXN + 1], dfn[MAXN + 1], scc[MAXN + 1], cnt, deg[MAXN + 1], idx;

std::vector<int> st;

inline void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++idx, st.push_back(u);
    register bool flag = 0;
    register int v;
    for (register int i = 0; i < edge[u].size(); i++) {
        if ((v = edge[u][i]) == fa && !flag) {
            flag = 1;
            continue;
        }
        if (!dfn[v])
            tarjan(v, u), low[u] = std::min(low[u], low[v]);
        else
            low[u] = std::min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        cnt++;
        register int v;
        do
            v = st.back(), scc[v] = cnt, st.pop_back();
        while (!st.empty() && v != u);
    }
}

using IO::io;

inline void solve() {
    register int n, m;
    io >> n >> m;
    for (register int i = 1, u, v; i <= m; i++) io >> u >> v, addEdge(u, v);
    tarjan(1, 1);
    for (register int i = 1; i <= n; i++)
        for (register Iterator p = edge[i].begin(); p != edge[i].end(); p++)
            if (scc[i] != scc[*p]) deg[scc[i]]++, deg[scc[*p]]++;
    register int ans = 0;
    for (register int i = 1; i <= cnt; i++)
        if (deg[i] == 2) ans++;
    io << (ans + 1) / 2;
}
}

int main() {
    // freopen("graph.in", "r", stdin);
    // freopen("graph.out", "w", stdout);
    solve();
    return 0;
}

inline char encode(int x) {
    x += ' ';
    if (x >= '"') x++;
    if (x >= '\\') x++;
    return x;
}

int decode(char x) {
    if (x >= '\\') x--;
    if (x >= '"') x--;
    return x - ' ';
}

char s[1000000], *c = s;

inline void encode(int x, int p) {
    register int cnt = 0;
    static int buf[30];
    for (register int i = 0; i < p; i++) buf[++cnt] = x % 93, x /= 93;
    while (cnt) *c++ = encode(buf[cnt--]);
}

inline int decode(const char *s, int p) {
    register int ret = 0;
    for (register int i = 0; i < p; i++) ret = ret * 93 + decode(s[i]);
    return ret;
}

/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「SuperOJ 2009」Math 24-10-2017
 *
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace {

int a, n, mod;

inline int modPow(int a, int b) {
    register int ret = 1;
    for (; b; b >>= 1, a = ((long long)a * a) & (mod - 1))
        (b & 1) ? ret = ((long long)ret * a) & (mod - 1) : 0;
    return ret;
}

inline void solveCase() {
    mod = 1 << n;
    if (a & 1) {
        std::cout << "1\n";
        return;
    }
    register int tmp = n / a;
    if (tmp * a < n) tmp++;
    register int ans = mod / (1 << tmp) - n / (1 << tmp);
    for (register int i = 1; i <= n; i++)
        if (modPow(a, i) == modPow(i, a)) ans++;
    std::cout << ans << '\n';
}

inline void solve() {
    register int T;
    std::cin >> T;
    while (T--) {
        std::cin >> a >> n;
        solveCase();
    }
}
}

int main() {
    // freopen("sample/1.in", "r", stdin);
    solve();
    return 0;
}