这场模拟赛是打过的感觉最好的一场模拟赛，虽然也挂了分但是从每个题里面都能或多或少的学到点什么。
写这个的时候已经忘了赛时干过什么了，来看题吧。
T1
场切了，但是貌似挂了不少人的分？
考虑 \(\gcd(a,b)\) 和 \(\operatorname{lcm}(a,b)\) 的实质，我们把 \(a,b\) 质因数分解为 \(a=p_1^{i_1}p_2^{i_2}p_3^{i_3}\cdots\)，\(b=p_1^{j_1}p_2^{j_2}p_3^{j_3}\cdots\)，于是有：
回到这个题，我们先把 \(x\) 质因数分解：\(x=p_1^{k_1}p_2^{k_2}p_3^{k_3}\cdots\)
首先如果 \(p=1\)，那么当然只有自己是合法的，答案是 \(1\)。
如果 \(p>1\)，我们可以改变通过改变 \(x\) 的某个 \(p_i\) 上的 \(k_i\) 为 \(k_i\times p\) 或 \(\frac{k_i}{p}\) 来构造 \(y\)，改变为后者的条件是 \(k_i\) 可被 \(p\) 整除。
这里要理解一下，通过上面的式子手摸一下就明白了。
于是质因数分解完对于每一位乘法原理计算即可。注意特判 \(p=1\)。
code
Show me the code
#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
bool ispr[1000005];
int pl[1000005];
bitset<1000000> vis;
int num=0;
bool j(ll s){for(int i=2;i*i<=s;i++){if(s%i==0)return 0;}return 1;
}
void es(int n){memset(ispr,1 ,sizeof ispr);ispr[1]=0;for(int i=2;i<=n;i++){if(ispr[i])pl[++num]=i; for(int j=1;j<=num&&i*pl[j]<=n;j++){ispr[i*pl[j]]=0;if(i%pl[j]==0)break;}}
}
map<ll,ll> mp;
void diver(ll x){int c=1;while(x){if(j(x)){mp[x]++;break;}if(x%pl[c]==0){x/=pl[c];mp[pl[c]]++;}else c++;}return ;
}
int main(){// freopen("count.in","r",stdin);// freopen("count.out","w",stdout);ll x,p;cin>>x>>p;if(p==1){cout<<1;return 0;}es(1e5);diver(x);ll ans=1;for(auto v:mp){if(v.second%p==0)ans*=2;}cout<<ans;return 0;
}
T2
有一种做法是优先队列存下来两两相邻的数加和的最大值，考虑每次删去产生了最大值的那一对元素中较大的那一个，因为只有这样才可能让答案更优，即使删去后序列的权值变大。
赛时我还注意到了一个性质：如果我们能够构造出一个长度 \(\ge m\) 的，权值小于给定值的串，我们一定可以通过每次删去序列中最大值的方式，来将其变成一个长度正好为 \(m\) 的，权值小于给定值的串。
证明反证即可。
然后问题变成了给定一个权值 \(k\)，我们能构造出的最长的符合要求的串的长度是多少。
这里是最恶心的地方，因为题目中要求是一个环，不能直接贪心了。如果直接 DP 会有 \(O(n^3)\) 的时间复杂度。
有个很重要的观察是：在最长的符合要求的串中，序列的最小值是一定在串中的。
原因是因为是全局最小值，换成序列里的其它值一定不优。
于是我们完全可以钦定最长串的开头是最小值，也就是在最小值处断环成链，接下来想想怎么贪心。
还有一个好玩的小技巧是我们根据 \(\left \lfloor \frac{k}{2} \right \rfloor\) 的大小把序列的权值分类，接下来所有的权值 \(\le \left \lfloor \frac{k}{2} \right \rfloor\) 的元素都可以之间选进合法序列里去了，原因显然。
接下来考虑已经放进去的元素之间那些段里面权值 \(\ge \left \lfloor \frac{k}{2} \right \rfloor\)，我们尝试把里面最小的元素放进去，如果这个元素和两边的加和 \(\le k\)，那么可以放进去，反正不能，如此贪心即可。
但是 code 还没调过，可能不会再调了罢。
code
Show me the code