2019 BUAA Spring Training 2 题解

Solved	A	B	C	D	E	F	G
7/7	Ø	Ø	Ø	Ø	Ø	Ø	Ø

O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet

比赛链接

A

题目描述
有$n$个人可以任选$2$的倍数，有$m$个人可以任选$3$的倍数。任意两个人选的数不相同，求选择的最大数的最小值。（$0\leq n,m\leq 10^6,n+m>0$）

解题思路
枚举每一个$6$的倍数被选$2$的那帮人取了还是被选$3$的那帮人取了即可。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main(){
    int i,n,m,a,b;
    scanf("%d%d",&n,&m);
    a=n*2,b=m*3;
    for(i=6;i<=min(a,b);i+=6){
        if(a<=b)a+=2;
        else b+=3;
    }
    printf("%d",max(a,b));
    return 0;
}

B

题目描述

$g^0(x)=x,g^n(x)=a\times g^{n-1}(x)+b$。输入$a,b,n,x$，求$g^n(x)$。（$1\leq a,b\leq 10^9,1\leq n\leq 10^{18}$，对$1e9+7$取模）

解题思路

手推一下式子，很显然的等比数列求和。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a,b,n,w=1000000007,x;
ll qp(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1,a=a*a%w)if(b&1)ans=ans*a%w;
    return ans;
}
ll inv(ll x){return qp(x,w-2);}
int main(){
    scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&x);
    if(a==1)printf("%I64d",(x+n%w*b)%w);
    else{
        ll apn=qp(a,n);
        ll ans=apn*x%w+b*(apn-1)%w*inv(a-1)%w;
        printf("%I64d",(ans%w+w)%w);
    }
    return 0;
}

C

题目描述

给一个长度$n\leq 10^5$的数列$a_i(0<a_i\leq 10^5)$。定义$f(l,r)$为$[l,r]$中任意一个数$i$，不存在一个$[l,r]$中与$i$不同的数$j$使得$a_i%a_j==0$。求$\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j)%(10^9+7)$。

解题思路

考虑每一个位置$i$对答案的贡献，即为向左右延伸长度的乘积。

故可以考虑左右两侧最靠近$i$且满足$a[i]%a[j]==0$的数字$j$，分别定为$l[i],r[i]$，用一个$loc$数组记录每一个数字最后出现的位置，递推求出即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll w=1000000007;
#define N 100010
#define M 10010
int a[N],n,l[N],r[N],loc[M];
int main(){
    int i,j;
    while(~scanf("%d",&n)){
        ll ans=0;
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        memset(loc,0,sizeof(loc));
        for(i=1;i<=n;i++){
            l[i]=0;
            for(j=1;j*j<=a[i];j++){
                if(a[i]%j==0){
                    if(loc[j]&&loc[j]>l[i])l[i]=loc[j];
                    if(loc[a[i]/j]&&loc[a[i]/j]>l[i])l[i]=loc[a[i]/j];
                }
            }
            loc[a[i]]=i;
        }
        memset(loc,0,sizeof(loc));
        for(i=n;i;i--){
            r[i]=n+1;
            for(j=1;j*j<=a[i];j++){
                if(a[i]%j==0){
                    if(loc[j]&&loc[j]<r[i])r[i]=loc[j];
                    if(loc[a[i]/j]&&loc[a[i]/j]<r[i])r[i]=loc[a[i]/j];
                }
            }
            loc[a[i]]=i;
        }
        for(i=1;i<=n;i++)ans=(ans+(i-l[i])*(r[i]-i)%w)%w;
        printf("%lld\n",ans);
    }
    return 0;
}

D

题目描述

给一个正整数$n$，问有没有一种选择数组$a_i,b_i(i∈[1,k])$的方案满足

$b_i$是$n$的因数
$1\leq a_i<b_i$
$\sum_{i=1}^{k}\frac{a_i}{b_i}=1-\frac1n$

解题思路

显然如果能构成答案，则必定只需要两个分数（任意两个不同的分数都可相加成另一个合法的分数）。

于是本题化为$a_1x+a_2y=n-1$的解，用扩展欧几里得即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a,b,n,g;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll g=exgcd(b,a%b,x,y),tmp=x;
    x=y;y=tmp-a/b*y;
    return g;
}
int main(){
    ll i;
    while(~scanf("%I64d",&n)){
        int flag=0;
        for(i=2;i*i<n;i++){
            if(n%i)continue;
            ll x,y;
            a=i,b=n/i,g=exgcd(a,b,x,y);
            a/=g;b/=g;
            if((n-1)%g)continue;
            x*=(n-1)/g;y*=(n-1)/g;
            if(x<0){
                ll k=-x/b+(x%b!=0);
                x+=k*b;
                y-=k*a;
            }
            if(y<0){
                ll k=-y/a+(y%a!=0);
                x-=k*b;
                y+=k*a;
            }
            if(x<0||y<0)continue;
            printf("YES\n2\n");
            printf("%I64d %I64d\n",y,a*g);
            printf("%I64d %I64d\n",x,b*g);
            flag=1;
            break;
        }
        if(!flag)printf("NO\n");
    }
    return 0;
}

E

题目描述
有$n$堆石子，每一堆取出$k$个石子之后就不能再恰好取出$k$个石子。轮流取石子，最后不能取的人输。问先手是否必输。

解题思路
手推一下，一堆石头最多可以被拿走$k$次，则贪心地从小到大拿，有$(1+2+…+k)\leq s_i\leq (1+2+…+k+1)$。

把每一堆的数量变成相对应的$k$，就变成简单的$Nim$游戏了。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
int x[]={0,2,5,9,14,20,27,35,44,54,65};
int n,t,a;
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d",&a);
        t^=std::lower_bound(x,x+10,a)-x;
    }
    printf("%s",t?"NO":"YES");
    return 0;
}

F

题目描述
$T\leq 50$组询问，每次询问一个区间$[l,r],1\leq l\leq r\leq 10^9$，问这个区间里有多少整数$x$满足$x%f(x)=0$，其中$f(x)$表示$x$的各位数之和。

解题思路
观察到$f(x)$只有$81$种选择，可以用数位$DP$，$f[pos][sum][div][r]$表示枚举到第$pos$位，当前已经有的数位和为$sum$时，$f(x)=div$，$x%f(x)=r$的$x$的个数。

注意不是所有时候$dfs$的结果都可以添加到记忆化搜索中的，只有不在限制下的才能成为通用解。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int dp[10][82][82][81];
int num[10],top;
int dfs(int pos,int sum,const int div,int r,int end){//end:是否为限制位
    int i,mx=9,&ans=dp[pos][sum][div][r];
    if(pos<0)return !r&&!sum;
    if(end)mx=num[pos];
    if(!end&&~ans)return ans;
    int temp=0;
    for(i=0;i<=mx&&i<=sum;i++)temp+=dfs(pos-1,sum-i,div,(r*10+i)%div,end&&(i==mx));
    //枚举这一位取值
    if(!end)ans=temp;//通用解
    return temp;
}
int f(int x){
    if(!x)return 0;
    int i,ans=0;
    top=-1;
    while(x)num[++top]=x%10,x/=10;
    for(i=1;i<=9*top+num[top];i++)ans+=dfs(top,i,i,0,1);
    return ans;
}
int main(){
    int t,l,r,cas=0;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&l,&r);
        printf("Case %d: %d\n",++cas,f(r)-f(l-1));
    }
    return 0;
}

G

题目描述
求$lcm$的二维前缀和。

解题思路
$f(n,m)$

$=\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$

$=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{gcd(i,j)}$

$=\sum_{g=1}^{min(n,m)}g\times \sum_{i=1}^{n}\sum_{j=1}^{m}i\times j(gcd(i,j)==g)$

$=\sum_{g=1}^{min(n,m)}g\times \sum_{i=1}^{\frac ng}\sum_{j=1}^{\frac mg}i\times j(gcd(i,j)==1)$

$=\sum_{g=1}^{min(n,m)}g\times u(\frac ng,\frac mg)$

$u(n,m)$

$=\sum_{i=1}^{n}\sum_{j=1}^{m}i\times j(gcd(i,j)==1)$

$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k|gcd(i,j)}i\times j\times \mu(k)$

$=\sum_{k=1}^{min(n,m)}\mu(k)\times k^2\sum_{i=1}^{\frac nk}\sum_{j=1}^{\frac mk}i\times j$

于是预处理$\mu(k)\times k^2$，分块处理后半段即可。

其中：$\sum_{i=1}^{x}\sum_{j=1}^{y}i\times j$

$=(1+2+…+x)(1+2+…+y)$

$=\frac{(1+x)x}2\frac{(1+y)y}2$

分别对$f(n,m)$，$u(n,m)$分块，复杂度$O(n)$。

$upd:$必须吐槽一波$bzoj$，下面的代码交上去会$CE$，原因就在于全局变量数组不能初始化，，，什么玩意，，，只好手动猜测$CE$原因，，贡献了一大波$CE&WA$

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 10000010
ll mu[N]={0,1},w=20101009;
int pr[N/10],a[N]={1,1},cnt;
ll inv;
ll qp(ll a,ll b){
    if(inv)return inv;
    ll ans=1;
    for(;b;b>>=1,a=a*a%w)if(b&1)ans=ans*a%w;
    return inv=ans;
}
ll F(int x){
    return qp(2,w-2)*x%w*(x+1)%w;
}
ll u(int n,int m){
    int i,r;ll ans=0;
    for(i=1;i<=n;i=r+1){
        r=min(n/(n/i),m/(m/i));
        ans=(ans+(mu[r]-mu[i-1])*F(n/i)%w*F(m/i)%w+w)%w;
    }
    return ans;
}
ll f(int n,int m){
    int i,r;ll ans=0;
    for(i=1;i<=n;i=r+1){
        r=min(n/(n/i),m/(m/i));
        ans=(ans+u(n/i,m/i)*(r-i+1)%w*(r+i)%w*qp(2,w-2))%w;
    }
    return ans;
}
int main(){
    int i,j,n,m;
    scanf("%d%d",&n,&m);
    if(n>m)n^=m^=n^=m;
    for(i=2;i<=m;i++){
        if(!a[i])pr[cnt++]=i,mu[i]=-1;
        for(j=0;j<cnt&&i*pr[j]<=m;j++){
            a[i*pr[j]]=1;
            if(i%pr[j]==0)break;
            mu[i*pr[j]]=mu[i]*-1;
        }
    }
    for(i=1;i<=m;i++){
        mu[i]=(mu[i]+w)*i%w*i%w;
        mu[i]=(mu[i]+mu[i-1])%w;
    }
    printf("%lld",f(n,m));
    return 0;
}