题目来源：https://vjudge.net/contest/536804

A题 Epic Game

题面：Simon and Antisimon play a game. Initially each player receives one fixed positive integer that doesn't change throughout the game. Simon receives number a and Antisimon receives number b. They also have a heap of n stones. The players take turns to make a move and Simon starts. During a move a player should take from the heap the number of stones equal to the greatest common divisor of the fixed number he has received and the number of stones left in the heap. A player loses when he cannot take the required number of stones (i. e. the heap has strictly less stones left than one needs to take).

Your task is to determine by the given a, b and n who wins the game.

1.模拟题，辗转相除法求gcd

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

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

int main(){
    int a,b,n,res,i=1;
    cin>>a>>b>>n;
    while(i){
        if(i%2){
            int res=gcd(a,n);
            //cout<<n<<" "<<res<<" "<<i<<endl;
            if(n>=res)
                n-=res;
            else{
                cout<<1;
                break;
            }
        }
        else{
            int res=gcd(b,n);
            //cout<<n<<" "<<res<<" "<<i<<endl;
            if(n>=res)
                n-=res;
            else{
                cout<<0;
                break;
            }
        }
        i++;
    }
}

B题 Die Roll

题面：Yakko, Wakko and Dot, world-famous animaniacs, decided to rest from acting in cartoons, and take a leave to travel a bit. Yakko dreamt to go to Pennsylvania, his Motherland and the Motherland of his ancestors. Wakko thought about Tasmania, its beaches, sun and sea. Dot chose Transylvania as the most mysterious and unpredictable place.

But to their great regret, the leave turned to be very short, so it will be enough to visit one of the three above named places. That's why Yakko, as the cleverest, came up with a truly genius idea: let each of the three roll an ordinary six-sided die, and the one with the highest amount of points will be the winner, and will take the other two to the place of his/her dreams.

Yakko thrown a die and got Y points, Wakko — W points. It was Dot's turn. But she didn't hurry. Dot wanted to know for sure what were her chances to visit Transylvania.

It is known that Yakko and Wakko are true gentlemen, that's why if they have the same amount of points with Dot, they will let Dot win.

约分即分子分母同时除以gcd

int a,b,n,res,i=1;
    bool flag=false;
    cin>>a>>b;
    int fz=max(a,b);
    if(fz==6)cout<<"1/6",flag=true;
    if(fz==1)cout<<"1/1",flag=true;
    res=gcd(7-fz,6);
    if(!flag)cout<<(7-fz)/res<<"/"<<6/res;

C题 Station of Fate

题面：There are nn people standing in mm stations, forming mm queues.You don't know which person is in which station, or in what order they are standing in queue, so you want to count the number of different schemes.Two schemes are considered different, if and only if there exists a station whose queue consists of different people, or has different orders.Calculate the number of different schemes modulo 998, 244, 353998244353.

1.n个人排成m队，可以看做n个人随机排列，形成n-1个空位，插空法选择其中m-1个空位，即可将之分成m个不同顺序组合，随机排列有$n!$种做法，插空有种$C^{m-1}_{n-1}$种做法。

2.数据范围是1e5，所以我们可以先预处理阶乘数组以及阶乘数组的逆元数组（费马小定理配合快速幂求解），利用组合数公式$C^m_n=\frac {n!}{(n-m)!m!}$即可得出组合数，时间复杂度O(nlogn)

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

using namespace std;

typedef long long LL;

const int N = 1e5+10,mod=998244353;

int n,m,a,b,jc[N],ijc[N];

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

LL c(int a,int b){
    return (LL)jc[a]*ijc[a-b]%mod*ijc[b]%mod;
}

int main(){
    cin>>n;
    jc[0]=ijc[0]=1;
    for (int i = 1; i < N; i ++ ){
        jc[i]=(LL)jc[i-1]*i%mod;
        ijc[i]=(LL)ijc[i-1]*qsm(i,mod-2,mod)%mod;
    }

    while(n--){
        cin>>a>>b;
        cout<<(LL)(jc[a]*c(a-1,b-1))%mod<<endl;
    }
    return 0;

}

D题 The last digit

题面：Nestor was doing the work of his math class about three days but he is tired of make operations a lot and he should deliver his task tomorrow. His math’s teacher gives him two numbers a and b. The problem consist of finding the last digit of the potency of base a and index b. Help Nestor with his problem. You are given two integer numbers: the base a (0 <= a <= 20) and the index b (0 <= b <= 2,147,483,000), a and b both are not 0. You have to find the last digit of ab.

1.最后一位数字不断自乘并对10取模即可

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

using namespace std;

typedef long long LL;

const int N = 1e5+10,mod=998244353;

int n,m,a,b,jc[N],ijc[N];

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



int main(){
    cin>>n;

    while(n--){
        cin>>a>>b;
        cout<<qsm(a,b,10)<<endl;
    }
    return 0;

}

题面：Calculate R := B P mod M for large values of B, P, and M using an efficient algorithm. (That’s right, this problem has a time dependency !!!.)

1.快速幂裸题

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

using namespace std;

typedef long long LL;

const int N = 1e5+10,mod=998244353;

int n,m,a,b,jc[N],ijc[N];

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



int main(){


    while(cin>>a>>b>>m){
        cout<<qsm(a,b,m)<<endl;
    }
    return 0;

}

F题 乘法逆元 2

题面：这可能是一道模板题。

给定 nn 个正整数 a_iai​，求每个数在模 pp 意义下的乘法逆元。

提示：请使用高效的读入方式。

1.数据范围有点大，直接暴力对每个数求一遍逆元nlogn会超时（做不出来于是求助度娘了hhh）

2.令$S=\prod_{i=1}^{n}a_i$