Codeforces Round #818 (Div. 2) A-E
题目
A
问有多少对\(1\leq a,b \leq n\)，满足\(\frac{lcm(a,b)}{gcd(a,b)}\leq3\)
已知\(lcm(a,b)=a*b/gcd(a,b)\)，原式可化为\(\frac{a*b}{gcd(a,b)^2} \leq3\)
令\(d=gcd(a,b),a=A*d,b=B*d,A,B互质\),原式可化为\(A*B<=3\),则\(A,B\)尽可分别为\((1,1)(1,2)(2,1)(1,3)(3,1)\),\((1,1)\)共有n种组合，\((1,2),(2,1)\)各有\(n/2\)的组合，\((1,3)(3,1)\)各有\(n/3\)个组合，因此最终答案
$ n + (n/2+n/3)*2$
void Solve(){
ll n;cin>>n;
cout<<(n/2+n/3)*2+n<<endl;
}
B
问对于一个边长为n的正方形点阵，给定一个位置\((r,c)\)为\(X\),求放置最少的\(X\)的个数使得对于任意长为k，宽为1的矩形里至少有一个\(X\), 输出放置后的图形。
分析样例可以看出斜着放最优，因此每次连续斜着放，然后对于已知点横向每k个放一个\(X\)，保证最小放置。
int n,k,r,c;
char g[maxn][maxn];
int vis[maxn][maxn];
void dfs(int x,int y){
if(vis[x][y]) return;
vis[x][y]=1;g[x][y]='X';
dfs((x+1)%n,(y+1)%n);
}
void solve(){
cin>>n>>k>>r>>c;
r--;c--;
rep(i,0,n-1){
rep(j,0,n-1){
vis[i][j]=0;
g[i][j]='.';
}
}
while(1){
if(vis[r][c]) break;
dfs(r,c);
r=(r+k)%n;
}
rep(i,0,n-1){
rep(j,0,n-1) putchar(g[i][j]);
pts;
}
}
C
给定长度为n的数组a,b；对于每一个\(a_i\)，如果\(a_i\leq a_{(i+1)\%n}\)那么\(a_i\)可以变为\(a_i + 1\),询问是否可以将数组a变为数组b
首先a种元素只能变大，因此如果\(a_i>b_i\)则非法。
其次因为\(a_i\)大小由\(a_{i+1}\)决定，且最终\(a_i\)最大为\(a_{i+1}+1\)，因此当\(a_i<b_i \& b_i>b_{i+1}+1\)时，非法。
其余情况均合法。
int Solve(){
int n;cin>>n;
vector<int>a(n+1);
vector<int>b(n+2);
rep(i,1,n) cin>>a[i];
rep(i,1,n) cin>>b[i];
rep(i,1,n) {
if(a[i]>b[i]) return 0;
}
b[n+1]=b[1];
rep(i,1,n){
if(b[i]>b[i+1]+1 && a[i]<b[i]) return 0;
}
return 1;
}
D
有 \(2^n\)个人进行二进一淘汰赛，每一场淘汰赛分为左边和右边，你可以决定每一场淘汰赛的双方及左边赢还是右边赢，你的目标是让最后胜出的人编号最小。
而主办方有k次修改比赛的机会，修改为将比赛双方位置互换，并且主办方希望最后胜出的选手编号尽可能地大。
对于每一个n，你需要给出在你精心设计比赛后，主办方修改k次比赛后能得到的最大的选手编号。
题意可化为一颗二叉树，当k=0时，最小编号为1，当k=1时，那么对于参赛者1走n层，每一层的比赛均可以修改来源，那么在这n层种可以有\(C(n,1)\)种选择改变胜者，那么最大的标号就是\(1+C(n,1)\)，以此类推，若k=2，那么相当于在n层中间选两层进行方向转变，那么有\(C(n,2)\)种选法，此时需要将这些选法一一赋值，故此时最大标号为\(1+C(n,1)+C(n,2)\)
综上，答案即为\(\sum_{i=0}^{min(n,k)} C(n,i)\)
void solve(){
com.build();
int n,k;
cin>>n>>k;
ll ans=1;
rep(i,1,min(n,k)){
ans+=com.C(n,i);
ans%=mod;
}
cout<<ans;
}
E
给定n，求对于所有\(a+b+c=n\)的三元组\((a,b,c)\)求\(\sum lcm(c,gcd(a,b))\)
对于\(lcm(c,gcd(a,b))\)，我们令
\(d=gcd(a,b),a=x*d,b=y*d,gcd(x,y)=1\)
已知一个数的因子是根号级的，那么我们可以枚举\(c\)，然后再遍历\(n-c\)的因子作为d，可以得到对应的\(lcm\)，则\(x+y=(n-c)/d\),那么剩下即求如何将\((n-c)/d\)分为两个互质的数的和。
因为\(x,y\)互质，则\(gcd(x,y)=gcd(x+y,y)=gcd((n-c)/d,y)=1\),那么将一个数\(z\)分成两个互质的数的和的方法数为\(\phi(z)\).
综上所述，枚举\(c\)再枚举\(n-c\)的因数\(d\)，然后累计答案即可
int p[maxm],cnt=0;
int vis[maxm],phi[maxm];
void pre(){
rep(i,2,N){
if(!vis[i]) p[++cnt]=i,phi[i]=i-1;
rep(j,1,cnt){
if(1LL*i*p[j]>N) break;
vis[i*p[j]]=1;
if(i%p[j]==0) {phi[i*p[j]]=phi[i]*p[j];break;}
else phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}
vector<int>G[maxn];
int gcd(int a,int b){return b? gcd(b,a%b):a;}
ll lcm(int a,int b){
return 1LL*a*b/gcd(a,b);
}
void Solve(){
pre();
int n;cin>>n;
rep(i,1,n){
for(int j=i;j<=n;j+=i){
G[j].pb(i);
}
}
ll ans=0;
rep(i,1,n) {
for(auto x:G[n-i]){
ans=(ans + 1LL*lcm(i,x) * phi[(n-i)/x])%mod;
}
}
cout<<ans<<endl;
}