首页 > 代码库 > Codeforces Round #422 (Div. 2) D. My pretty girl Noora

Codeforces Round #422 (Div. 2) D. My pretty girl Noora

2024-10-17 12:08:02   212人阅读

题目链接：Codeforces Round #422 (Div. 2) D. My pretty girl Noora

题意：

给你一个数n和t,l,r，让你求 t0·f(l)?+?t1·f(l?+?1)?+?...?+?tr?-?l·f(r). 

其中f(n)是n个人的最少比较次数。

比如n为4,可以先2 2分，然后胜出2个人，最后再比较一次，所以f(4)=3。

f(3)=3,因为3为质数，只能这样分。

题解：

这题半天没看清楚题意啊。- -！以为是任意分。

结果是选一个数x,每组都必须为x个人。

然后正确理解题意后就好做了。

显然将n分的越小答案越优。

所以就有了代码中的dp，具体解释看代码。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 typedef long long ll;
 5 const int N=5e6+7,P=1e9+7;
 6 
 7 ll dp[N],f[N];
 8 int a,l,r;
 9 
10 int primes[N+1],tot=0,fac[N];
11 bool vis[N+1];
12 void Euler(){
13     F(i,2,N){
14         if(!vis[i])primes[++tot]=i;
15         F(j,1,tot){
16             if(i*primes[j]>N)break;
17             vis[i*primes[j]]=1;
18             if(i%primes[j]==0)break;
19         }
20     }
21 }
22 
23 int main()
24 {
25     Euler();
26     scanf("%d%d%d",&a,&l,&r);
27     dp[2]=1,dp[3]=3,dp[4]=3;
28     F(i,5,r)if(vis[i])
29     {
30         F(j,1,tot)if(i%primes[j]==0)
31         {
32             fac[i]=primes[j];break;//选取最小的因子。
33         }
34     }
35     F(i,5,r)
36     {
37         if(!vis[i])dp[i]=1ll*i*(i-1)/2%P;//i为质数
38         else dp[i]=(i/fac[i]*dp[fac[i]]+dp[i/fac[i]])%P;//i为合数
39     }
40     f[0]=1;
41     F(i,1,r)f[i]=f[i-1]*a%P;
42     ll ans=0;
43     F(i,l,r)ans=(ans+f[i-l]*dp[i])%P;
44     printf("%I64d\n",ans);
45     return 0;
46 }
View Code

 

Codeforces Round #422 (Div. 2) D. My pretty girl Noora


联系
我们