B 华华对月月的忠诚：
试着打了打表，发现只跟gcd(a,b)有关，所以直接输出gcd(a,b)就可以了。

但是作为题解要数学证明，我在别人的博客那发现了证明：

https://blog.nowcoder.net/n/69e53616e1444d399be566a360061220
大家想要看数学证明的可以去看看。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

char s[maxn];

ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}

int main(){
    ll a,b;
    scanf("%lld%lld%s",&a,&b,&s);
    printf("%lld",gcd(a,b));
    return 0;
}

C. Game
很基础的质因数分解，然后直到什么时候分解不了了就输出就好了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int a[maxn];

int check(int num){
    for(int i=2;i*i<=num;i++){
        if(num%i==0){
            return num/i;
        }
    }
    return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    int flg=0;
    while(1){
        int tmp=check(n);
        if(tmp==0) break;
        n=tmp;
        flg++;
    }
    if(flg%2==1){
        printf("Johnson\n");
    }
    else{
        printf("Nancy\n");
    }
    return 0;
}

D 挖沟
超级明显的最小生成树题，有两种算法：普利姆和克鲁斯卡尔，复杂度分别是O(n²)和O(mlogm)。所以这次的是要用克鲁斯卡尔。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int fa[maxn];

void init()
{
    for(int i = 0;i<=maxn;i++){
        fa[i]=i;
    }
}
int find(int x)
{
    return (fa[x] == x)?x:fa[x] = find(fa[x]);
}
void merge(int y,int x)
{
    int xx = find(x),yy = find(y);
    if(xx != yy) fa[xx] = yy;
}

struct Node{
    int x,y,val;
    Node(int x,int y,int val):x(x),y(y),val(val){
    }
    bool operator<(const Node& bb)const{
        return val>bb.val;
    }
};

int main(){
    init();
    int n,m;
    scanf("%d%d",&n,&m);
    priority_queue<Node> q;
    for(int i=1;i<=m;i++){
        int x,y,val;
        scanf("%d%d%d",&x,&y,&val);
        q.push(Node(x,y,val));
    }
    int ans=0;
    while(!q.empty()){
        int x=q.top().x;int y=q.top().y;int val=q.top().val;
        q.pop();
        int xx=find(x);int yy=find(y);
        if(xx!=yy){
            fa[yy]=xx;
            ans+=val;
        }
    }
    printf("%d\n",ans);
    return 0;
}

E 签到题
E是最有意思的题了，主要看大家是否看到这句话：保证数据随机生成。
一般看到这句话就意识到：暴力说不定能行。
然后试着暴力一发，A了。
正常的时间复杂度：如果随机的话，平均的L-R长度为1e5/2，有N次操作，那么应该是1e9的时间复杂度，但是随机嘛肯定会小点，所以暴力是能过的，脸黑的就再交一次。

#include <algorithm>
 #include <iostream>
 #include <cstring>
 #include <climits>
 #include <cstdio>
 #include <vector>
 #include <cstdlib>
 #include <ctime>
 #include <cmath>
 #include <queue>
 #include <stack>
 #include <map>
 #include <set>
 #define fi first
 #define lc (x<<1)
 #define se second
 #define U unsigned
 #define rc (x<<1|1)
 #define Re register
 #define LL long long
 #define MP std::make_pair
 #define CLR(i,a) memset(i,a,sizeof(i))
 #define FOR(i,a,b) for(Re int i = a;i <= b;++i)
 #define ROF(i,a,b) for(Re int i = a;i >= b;--i)
 #define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
 #define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
 #define DEBUG(x) std::cerr << #x << '=' << x << std::endl
 const int MAXN = 1000000+5;
 int N,maxL;
 std::set<std::pair<int,int> > L;
 inline int calc(){
     // 返回 set 中所有线段的并长度。(每个 pair 表示一个线段[first,second]
 }
int tmp[MAXN];
 int main(){
     scanf("%d%d",&N,&maxL);
     int res=0;
     while(N--){
         int opt,x,y;
         scanf("%d%d%d",&opt,&x,&y);
         if(opt == 1){
             if(L.find(MP(x,y)) != L.end()) continue;
             L.insert(MP(x,y));
             for(int i=x;i<=y;i++){
                tmp[i]++;
                 res+=tmp[i]==1;
             }
         }
         if(opt == 2){
             if(L.find(MP(x,y)) == L.end()) continue;
             L.erase(MP(x,y));
             for(int i=x;i<=y;i++){
                tmp[i]--;
                 res-=tmp[i]==0;
             }
         }
         if(opt == 3){
             printf("%d\n",res);
         }
     }
     return 0;
 }