记录生活中的美

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 10;
int cnt, primes[N];
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            for (int j = i; j <= n; j += i) st[j] = true;
        }
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    get_primes(b);
    for (int i = a; i <= b; i++) {
        int t = i;
        vector<int> res;

        for (int j = 0; j < cnt && primes[j] < t; j++) {
            if (t % primes[j] == 0) {
                while (t % primes[j] == 0) {
                    res.push_back(primes[j]);
                    t /= primes[j];
                }
            }
        }
        if (t > 1) res.push_back(t);

        cout << i << '=';
        for (int j = 0; j < res.size(); j++) {
            if (j > 0) cout << '*';
            cout << res[j];
        }
        cout << endl;
    }

    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;

const int N = 1e6 + 10;
int cnt, primes[N];
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            for (int j = i; j <= n; j += i) st[j] = true;
        }
    }
}

int main() {
    get_primes(1e6);
    int n;
    // 题目给出褪色者最终战胜葛瑞克所挑战的次数n。
    cin >> n;
    // 第几次打败葛瑞克
    int cnt = 1;
    // 当前接肢数量
    int cur = 2;
    // 接肢的数量是以指数递增
    int exp = 2;
    // 当前攻击的力度，必须是质数，所以就用primes[]数组的下标表示
    int idx = 0;
    map<int, int> mp;
    do {
        // 只有质数才会对BOSS造成伤害 整数解肢
        if (cur % primes[idx] == 0) {
            cur /= primes[idx];
            mp[primes[idx]]++;
            idx = 0;
        } else
            idx++;
        // 如果回到了1，证明被战胜了
        if (cur == 1) {
            cnt++;
            cur = 1;
            // 接肢的数量是以指数递增的
            cur *= (++exp);
        }
    } while (cnt != n);
    // 输出结果
    for (auto it : mp) cout << it.first << " " << it.second << endl;
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n, chushu = 1, weishu = 1;
    cin >> n;
    // 先找到一个比所求大的111...
    while (chushu < n) {
        chushu = chushu * 10 + 1;
        weishu++;
    }
    while (1) {
        // 再输出除以n的商
        cout << chushu / n;
        // 如果整除就返回
        if (chushu % n == 0) break;
        // 加一个 1 继续除
        chushu = (chushu % n) * 10 + 1;
        // 位数 + 1
        weishu++;
    }
    cout << ' ' << weishu;
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1, gcd;
    gcd = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return gcd;
}
int main() {
    int a, b, x, y;
    while (cin >> a >> b) {
        exgcd(a, b, x, y);
        cout << x << " " << y << " " << a * x + b * y << endl;
    }
    return 0;
}

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

using namespace std;

const int N = 2010;

int c[N][N];
// 前缀和
int s[N][N];

int main() {
    int T, k;
    scanf("%d%d", &T, &k);

    // 预处理前缀和
    
    for (int i = 0; i < N; i++)
        // 求余数
        for (int j = 0; j <= i; j++) {
            if (j == 0)
                c[i][j] = 1 % k;
            else
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
            // 如果是余数0，就代表就有一次
            if (c[i][j] == 0) s[i][j] = 1;
        }
    // 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            if (i != 0) s[i][j] += s[i - 1][j];
            if (j != 0) s[i][j] += s[i][j - 1];
            if (i != 0 && j != 0) s[i][j] -= s[i - 1][j - 1];
        }

    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);

        printf("%d\n", s[n][m]);
    }

    return 0;
}

#include <iostream>
using namespace std;

int main()
{
    string s;
    cin >> s;
    cout << s[6] << s[7] << s[8] << s[9] << '-';
    cout << s[0] << s[1] << '-';
    cout << s[3] << s[4] << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if(a > b) swap(a,b);
    if(b > c) swap(b,c);
    if(a > b) swap(a,b);
    cout << a << "->" << b << "->" << c << endl;
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    for (int i = 0; i < s.size(); i++) {
        bool flag = false;
        int cnt = 1;
        int j = i + 1;
        if (s[i] == '6') {
            while (s[j++] == '6') cnt++;
            if (cnt > 9) {
                flag = true;
                cout << "27";
            } else if (cnt > 3) {
                flag = true;
                cout << "9";
            }
        }
        if (flag) {
            i = j - 2;
            continue;
        }
        cout << s[i];
    }
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#define x first
#define y second
using namespace std;
// 准考证 考试座位号
typedef pair<string, string> PII;
// 座位号
map<int, PII> m;

int main() {
    int N;
    cin >> N;
    while (N--) {
        string a, c;
        int b;
        cin >> a >> b >> c;
        m[b] = {a, c};
    }
    int M;
    cin >> M;
    while (M--) {
        int a;
        cin >> a;
        cout << m[a].x << " " << m[a].y << endl;
    }
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#define x first
#define y second
using namespace std;

map<int, int> m;

int main() {
    int N;
    cin >> N;
    while (N--) {
        int t;
        cin >> t;
        m[t]++;
    }
    cout << m.begin()->x << ' ' << m.begin()->y << endl;
    cout << m.rbegin()->x << ' ' << m.rbegin()->y << endl;
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;

int n, m, q;
set<int> r, c;
int main() {
    cin >> n >> m >> q;
    int T, C;
    while (q--) {
        cin >> T >> C;
        if (T == 0) {
            r.insert(C);
        } else {
            c.insert(C);
        }
    }
    cout << (n - r.size()) * (m - c.size()) << endl;
    return 0;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    getline(cin, s);
    while (n--) {
        string s;
        getline(cin, s);

        // 无论用户说什么，首先把对方说的话在一行中原样打印出来；
        cout << s << endl;

        // 把行首尾的空格全部删掉
        // s.erase(1);  删除集合s中的1这个元素
        // s.erase(s.begin()); 删除集合s中的第一个元素
        // s.erase(s.end() - 1); 删除集合s中的最后一个元素
        while (s[0] == ' ') s.erase(s.begin());
        while (s[s.size() - 1] == ' ') s.erase(s.end() - 1);
        // 把相邻单词间的多个空格换成 1 个空格，把标点符号前面的空格删掉；
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                while (s[i + 1] == ' ') s.erase(s.begin() + i + 1);
                // isalnum() 函数用于检测字符串是否只包含字母和数字。
                // !isalnum() 检测是否是空格和标点符号。
                if (!isalnum(s[i + 1])) s.erase(s.begin() + i);
            }
        }

        // 把原文中所有大写英文字母变成小写，除了 I；
        for (int i = 0; i < s.size(); i++)
            // isupper() 函数检测是否是大写字母。
            if (isupper(s[i]) && s[i] != 'I')
                s[i] = tolower(s[i]);  // tolower() 函数用于把字符转换为小写。

        // 把原文中所有独立的 can you、could you 对应地换成 I can、I could——
        // 这里“独立”是指被空格或标点符号分隔开的单词；
        for (int beg = 0;; beg++) {
            beg = s.find("can you", beg);
            if (beg == -1) break;
            if ((beg == 0 || !isalnum(s[beg - 1])) &&
                (beg + 7 == s.size() || !isalnum(s[beg + 7]))) {
                s.replace(beg, 7, "A can");
            }
        }
        // 由于后面还要处理'I'这里先用'A'代替'I'，最后在变成'I'
        for (int beg = 0;; beg++) {
            beg = s.find("could you", beg);
            if (beg == -1) break;
            if ((beg == 0 || !isalnum(s[beg - 1])) &&
                (beg + 9 == s.size() || !isalnum(s[beg + 9]))) {
                s.replace(beg, 9, "A could");
            }
        }
        // 把原文中所有独立的 I 和 me 换成 you；
        for (int beg = 0;; beg++) {
            beg = s.find("I", beg);
            if (beg == -1) break;
            if ((beg == 0 || !isalnum(s[beg - 1])) &&
                (beg + 1 == s.size() || !isalnum(s[beg + 1]))) {
                s.replace(beg, 1, "you");
            }
        }
        for (int beg = 0;; beg++) {
            beg = s.find("me", beg);
            if (beg == -1) break;
            if ((beg == 0 || !isalnum(s[beg - 1])) &&
                (beg + 2 == s.size() || !isalnum(s[beg + 2]))) {
                s.replace(beg, 2, "you");
            }
        }

        // 把原文中所有的问号 ? 换成惊叹号 !；
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') s[i] = '!';
            if (s[i] == 'A') s[i] = 'I';
        }

        // 在一行中输出替换后的句子作为 AI 的回答。
        cout << "AI: " << s << endl;
    }
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;

bool isPrime(LL t) {
    if (t < 2) return false;
    for (LL i = 2; i <= t / i; i++)
        if (t % i == 0) return false;
    return true;
}

int main() {
    LL t;
    cin >> t;
    cout << t << ' ' << (string)(isPrime(t) ? "yes" : "no") << endl;
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

void to_2(int n) {
    int a[1000];
    int num = 0;
    do {
        a[num++] = n % 2;
        n /= 2;
    } while (n != 0);
    for (int i = num - 1; i >= 0; i--) cout << a[i];
    cout << ' ';
    return;
}

void to_8(int n) {
    int a[1000];
    int num = 0;
    do {
        a[num++] = n % 8;
        n /= 8;
    } while (n != 0);
    for (int i = num - 1; i >= 0; i--) cout << a[i];
    cout << ' ';
    return;
}

char h[17] = {'0', '1', '2', '3', '4', '5', '6', '7',
              '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
void to_16(int n) {
    int a[1000];
    int num = 0;
    do {
        a[num++] = n % 16;
        n /= 16;
    } while (n != 0);
    for (int i = num - 1; i >= 0; i--) cout << h[a[i]];
    return;
}

int main() {
    int t;
    cin >> t;
    to_2(t);
    to_8(t);
    to_16(t);
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 4e7 + 10;

//primes数组用来存放质数
int primes[N], cnt;
//st[i], i为质数则为false否则为true
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        //假设primes[0]为n最小的质因子,i为最大的因数，
        //易知若primes[i]中i>0,则会进入循环后产生多余的标记。
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            //标记;primes[j]一定是primes[j]*i的最小质因子
            st[primes[j]*i] = true;
            //表明primes[j]一定是i的最小质因子,没有必要再遍历,primes要小于等于i的最小质因子
            //这样能保证每个数遍历一遍,而没有重复
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

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


int main() {
    int a,b;
    cin >> a >> b;
    cout << gcd(a,b) << ' ' << a * b / gcd(a,b)<< endl;
    return 0;
}

#pragma GCC optimize(2)
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int phi(int x) {
    int res = x;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

int main() {
    int n;
    cin >> n;
    int x;
    while (n--) {
        cin >> x;
        cout << phi(x) << endl;
    }

    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
int primes[N], cnt;  // primes数组存所有的质因子，cnt是下标
int phi[N];          //欧拉函数
bool st[N];          //表示每个数是否被筛掉了

LL get_eulers(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {  //线性筛
        if (!st[i]) {               //当前没有被筛过就是质数
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    LL res = 0;
    for (int i = 1; i <= n; i++) res += phi[i];
    return res;
}

int main() {
    int n;
    cin >> n;
    cout << get_eulers(n) << endl;
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;

int main() {
    string n;
    getline(cin, n);
    int cnt = 0;
    for (int i = 0; i < n.size(); i++) cnt += (n[i] - '0');
    stack<string> st;
    while (cnt) {
        switch (cnt % 10) {
            case 0:
                st.push("ling");
                break;
            case 1:
                st.push("yi");
                break;
            case 2:
                st.push("er");
                break;
            case 3:
                st.push("san");
                break;
            case 4:
                st.push("si");
                break;
            case 5:
                st.push("wu");
                break;
            case 6:
                st.push("liu");
                break;
            case 7:
                st.push("qi");
                break;
            case 8:
                st.push("ba");
                break;
            case 9:
                st.push("jiu");
                break;
        }
        cnt /= 10;
    }
    cout << st.top();
    st.pop();
    while (!st.empty()) {
        cout << " " << st.top();
        st.pop();
    }
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef struct st {
    string name, id;
    int score;
} st;

bool stu_sort(st a, st b) { return a.score > b.score; }

int main() {
    int n;
    st stu[10010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> stu[i].name >> stu[i].id >> stu[i].score;
    }
    sort(stu, stu + n, stu_sort);
    cout << stu[0].name << ' ' << stu[0].id << endl;
    cout << stu[n - 1].name << ' ' << stu[n - 1].id;

    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int T;
int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 得到某年某月的天数
int get(int year, int month) {
    if (month != 2)
        return months[month];
    else {
        // 2月
        int leap = (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
        return 28 + leap;
    }
}

void next_date(int year, int month, int date) {
    if (date == get(year, month)) {
        if (month == 12) {
            year++;
            month = 1;
        } else {
            month++;
        }
        date = 1;
    } else {
        date++;
    }
    printf("%04d-%02d-%02d\n", year, month, date);
}

int main() {
    cin >> T;
    while (T--) {
        int year, month, date;
        cin >> year >> month >> date;
        next_date(year, month, date);
    }
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int T;
int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 是否是闰年
bool leap(int year) {
    return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
}
// 得到某年某月的天数
int get(int year, int month) {
    if (month != 2)
        return months[month];
    else {
        // 2月
        return 28 + leap(year);
    }
}

int main() {
    int year1, month1, date1;
    int year2, month2, date2;
    scanf("%d-%d-%d", &year1, &month1, &date1);
    scanf("%d-%d-%d", &year2, &month2, &date2);

    if (year1 == year2) {
        if (month1 == month2) {
            cout << abs(date2 - date1) + 1;
            return 0;
        } else if (month1 < month2) {
            int ans = 0;
            ans += get(year1, month1) - date1;
            for (int i = month1 + 1; i < month2; i++) ans += get(year1, i);
            ans += date2;
            cout << ans + 1<< endl;
            return 0;
        } else if (month1 > month2) {
            int ans = 0;
            ans += get(year1, month2) - date2;
            for (int i = month2 + 1; i < month1; i++) ans += get(year1, i);
            ans += date1;
            cout << ans + 1<< endl;
            return 0;
        }
    } else if (year1 < year2) {
        int ans = 0;
        ans += get(year1, month1) - date1;
        for (int i = month1 + 1; i <= 12; i++) ans += get(year1, i);
        for (int i = year1 + 1; i < year2; i++) ans += 365 + leap(i);
        for (int i = 1; i < month2; i++) ans += get(year2, i);
        ans += date2;
        cout << ans + 1 << endl;
    } else if (year1 > year2) {
        int ans = 0;
        ans += get(year2, month2) - date2;
        for (int i = month2 + 1; i <= 12; i++) ans += get(year2, i);
        for (int i = year2 + 1; i < year1; i++) ans += 365 + leap(i);
        for (int i = 1; i < month1; i++) ans += get(year1, i);
        ans += date1;
        cout << ans + 1 << endl;
        return 0;
    }
    return 0;
}

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int g[11][11];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < 2 * n + 1; i++) {
        for (int j = 0; j < 2 * n + 1; j++) {
            int t = n - abs(i - n) - abs(j - n);
            if (t < 0)
                printf("  ");
            else
                printf("%d ", t);
        }
        puts("");
    }

    return 0;
}

#include <iostream>
using namespace std;

const int N = 10000 + 10;

int n, m, k;
int a[N];
bool vis[N];

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

// 线性筛筛素数
void get_primes() {
    for (int i = 2; i <= N; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= N / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
// 判断第 x 位上放 y 这个数字后是否还是反素数序列
bool check(int x, int y) {
    // 如果是第一位，那么不测
    if (x == 0) return true;
    // 只需检测前 k 个数的合
    int sum = y;
    for (int i = x - 1; x - i < k && i > 0; i--) {
        sum += a[i];
        // 只要在阶数范围内，有一个连续的合是素数就不是反素数序列
        if (!st[sum]) return false;
    }
    return true;
}

// x 表示当前判断到第几位
bool dfs(int x) {
    // 如果最后一位，则返回true
    if (x == n - m + 1) return true;
    // 如果没用过这个数字且放进去是反素数序列
    for (int i = m; i <= n; i++) {
        if (!vis[i] && check(x, i)) {
            a[x] = i;
            vis[i] = true;
            if (dfs(x + 1)) return true;

            vis[i] = false;
        }
    }
    return false;
}

int main() {
    get_primes();
    while (scanf("%d%d%d", &m, &n, &k) && (m + n + k)) {
        memset(vis, 0, sizeof(vis));
        if (dfs(0)) {
            for (int i = 0; i < n - m; i++) printf("%d,", a[i]);
            printf("%d\n", a[n - m]);
        } else {
            printf("No anti-prime sequence exists.\n");
        }
    }
    return 0;
}