时隔多年，终于又有了一套我能改完的题……

A.神炎皇

遇到这种要求整除的题显然拆出gcd

设$d=gcd(a,b)\ \ \ a'=\frac{a}{d} \ \ \ b'=\frac{b}{d}$

原式转化为$(a'd+b'd)|(a'db'd)$

$(a'+b')|(a'b'd)$

又因为$gcd(a',b')=1$

所以$a'+b'$一定不是$a'b'$的因子，进而得到$(a'+b')|d$

又由$a+b \leq n \rightarrow (a'+b')d \leq n \rightarrow a'+b' \leq \sqrt{n}$

不妨枚举$s=a'+b'$

那么满足$gcd(a',b')=1$的合法数对有多少个？

由更相减损术可得$gcd(a,b)=gcd(a+b,b)$

所以$a',b'$共$\varphi (s)$对

那合法的$d$也就只有$\frac{n}{s^2}$个

答案即$\sum \limits _{i=2}^{n} \varphi (i) \times \frac{n}{i^2}$

注意到当$i> \sqrt{n}$时每项为0，所以枚举到$\sqrt{n}$即可

复杂度$O(\sqrt{n})$。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=1e7+2;

ll n,ans,sqt;

int pr[N],vis[N],tot,phi[N];

void work()

{

	phi[1]=1;

	for(int i=2;i<=sqt;i++)

	{

		if(!vis[i])pr[++tot]=i,phi[i]=i-1;

		for(int j=1;j<=tot&&pr[j]*i<=sqt;j++)

		{

			vis[i*pr[j]]=1;

			if(i%pr[j])phi[i*pr[j]]=phi[i]*(pr[j]-1);

			else

			{

				phi[i*pr[j]]=phi[i]*pr[j];

				break;

			}

		}

		ans+=1LL*phi[i]*(n/(1LL*i*i));//cout<<ans<<endl;

	}

}

int main()

{

	scanf("%lld",&n);

	sqt=sqrt(n);

	work();

	/*for(int i=1;i<=n;i++)

		cout<<i<<' '<<phi[i]<<endl;*/

	cout<<ans<<endl;

	return 0;

}

B.降雷皇

就是LIS再加上求方案数……权值线段树可以一次性处理二者信息，每次查询当前序列值对应的最长公共子序列长度和方案数转移即可。注意区间查询左右边界问题。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<vector>

#define pa pair<int,int>

using namespace std;

const int N=1e5+5;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

typedef long long ll;

const ll mod=123456789;

int n,a[N],type,side;

int ans,f[N<<2],res=1;

ll num,g[N<<2];

#define ls(k) (k)<<1

#define rs(k) (k)<<1|1

void up(int k)

{

    f[k]=max(f[ls(k)],f[rs(k)]);

    if(f[ls(k)]>f[rs(k)])g[k]=g[ls(k)];

    else if(f[rs(k)]>f[ls(k)])g[k]=g[rs(k)];

    else g[k]=(g[ls(k)]+g[rs(k)])%mod;

}

void ins(int k,int l,int r,int pos,int valf,ll valg)

{

    if(l==r)

    {

        if(f[k]<valf)f[k]=valf,g[k]=valg;

        else if(f[k]==valf)(g[k]+=valg)%=mod;

        return ;

    }

    int mid=l+r>>1;

    if(pos<=mid)ins(ls(k),l,mid,pos,valf,valg);

    else ins(rs(k),mid+1,r,pos,valf,valg);

    up(k);

}

void ask(int k,int l,int r,int L,int R)

{

    if(L>R)return ;

    if(L<=l&&R>=r)

    {

        if(ans<f[k])ans=f[k],num=g[k];

        else if(ans==f[k])(num+=g[k])%=mod;

        return ;

    }

    int mid=l+r>>1;

    if(L<=mid)ask(ls(k),l,mid,L,R);

    if(R>mid)ask(rs(k),mid+1,r,L,R);

}

int main()

{

    n=read();type=read();

    for(int i=1;i<=n;i++)

        a[i]=read(),side=max(side,a[i]);

    int nowf=1;ll nowg=1;

    ins(1,1,side,a[1],nowf,nowg);

    for(int i=2;i<=n;i++)

    {

        ans=num=0;

        ask(1,1,side,1,a[i]-1);

        nowf=ans+1;nowg=max(1LL,num);

        //cout<<nowf<<' '<<nowg<<endl;

        res=max(res,nowf);

        ins(1,1,side,a[i],nowf,nowg);

    }

    printf("%d\n",res);

    if(!type)return 0;

    ans=num=0;

    ask(1,1,side,1,side);

    printf("%lld\n",num);

    return 0;

}

C.幻魔皇

神一样的思路

第一步就跪了……根本没想到可以枚举距离

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=5005;

const ll mod=123456789;

ll f[N],sum[N],ans[N<<1];

int n;

int main()

{

    scanf("%d",&n);

    f[1]=f[3]=1;sum[1]=sum[2]=1;sum[3]=2;

    for(int i=4;i<=n;i++)

        f[i]=(f[i-1]+f[i-2])%mod,sum[i]=(sum[i-1]+f[i])%mod;

    for(int i=1;i<n;i++)

        (ans[i]+=sum[n-i]*f[i+1]%mod)%=mod;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

        {

            int d1=i+j,d2=max(i,j);

            (ans[d1]+=(sum[n-d2+1]-1)*f[j+1]%mod*f[i]%mod)%=mod;

        }

    for(int i=1;i<=n*2;i++)

        printf("%lld ",ans[i]);

    putchar('\n');

    return 0;

}

巴特西

[CSP-S模拟测试67]题解

A.神炎皇

B.降雷皇

C.幻魔皇

最新文章

热门文章