Codeforces Round #422 (Div. 2)D. My pretty girl Noora（递推+数论）

传送门

题意

对于n个女孩，每次分成x人/组，每组比较次数为$\frac{x(x+1)}{2}$，直到剩余1人

计算$$\sum_{i=l}^{r}t{i-l}f(i)$$,其中f(i)代表i个女孩的最少比较数

分析

难度在于如何计算f(i)，f(i)每次除的是素数，详情见题解

那么我们对于每一个素数i，直接计算$f[i]=\frac{x(x+1)}{2}$

非素数,枚举能被i整除的第一个素数j，$f[i]=f[i/j]+i*(j-1)/2$

-end-

trick

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

//#pragma comment(linker, "/STACK:102400000,102400000")

//inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

const int maxn=5e6;

const ll mod =  1e9+7;

int prime[maxn+100];

bool p[maxn+100];

void get_prime()

{

   F(i,2,maxn)

   {

      if(!p[i]) prime[++prime[0]]=i;

      for(int j=1;j<=prime[0]&&i*prime[j]<=maxn;++j)

      {

         p[i*prime[j]]=1;

         if(i%prime[j]==0) break;

      }

   }

}

ll t;

int l,r;

ll f[maxn+100],ans;

int main()

{

    get_prime();

    //F(i,1,prime[0]) f[prime[i]]=(ll)prime[i]*(ll)(prime[i]-1)/2;

    scanf("%lld %d %d",&t,&l,&r);

    //F(i,1,100) printf("%d\n",p[i]);

    f[1]=1;

    for(int i=2;i<=maxn;++i)if(p[i])

    {

        for(int j=1;j<=prime[0];++j) if(i%prime[j]==0) {f[i]=1LL*i*(prime[j]-1)/2+f[i/prime[j]];break;}

    }

    else {f[i]=1LL*i*(i-1)/2%mod;};

    ll cnt=1;

    F(i,l,r)

    {

        ans=(ans+cnt*f[i])%mod;

        cnt=cnt*t%mod;

    }

    printf("%I64d\n",ans);

    return 0;

}

巴特西

Codeforces Round #422 (Div. 2)D. My pretty girl Noora（递推+数论）

传送门

题意

分析

trick

代码

最新文章

热门文章