首页 > 其他分享 >P9817 题解

P9817 题解

时间:2023-11-03 21:46:02浏览次数:40  
标签:暴力 题解 质数 sqrt P9817 复杂度

这里提供一个非常暴力但是期望复杂度很低的算法。

不难想到要么就是全部放 \(1\),要么就是取出一个最大的质数,然后对于剩下的部分继续按照这样的策略求答案。

因为质数间隔不大,然后暴力判断质数复杂度是 \(O(\sqrt n)\) 的,再加上 IOI 的 buff,我们可以直接考虑从大到小枚举质数,因为取到最后取的次数也不多,预期复杂度就是 \(O(\sqrt n)\) 乘上一个比较大的常数,实际情况跑的很快。

\(Code\)

bool check(int x){//暴力判断质数(1也算)
    if(x<=2)return 1;
    if(x+1&1)return 0;
    for(int j=3;j*j<=x;j+=2)if(x%j==0)return 0;
    return 1;
}
ll work(int n,int k,int i=0){//暴力递归求解
    if(!n)return 0;
    for(i=n;!check(i);--i);
    if(1ll*(i-k)*(i-k)<=1ll*i*(k-1)*(k-1))return 1ll*n*(k-1)*(k-1);
    return work(n-i,k)+1ll*(i-k)*(i-k);
}
int main(){
    for(int T=read();T--;){
        int n=read(),k=read();
        printf("%lld\n",work(n,k));
    }
    return 0;
}

标签:暴力,题解,质数,sqrt,P9817,复杂度
From: https://www.cnblogs.com/NBest/p/17808553.html

相关文章

  • [ARC104F] Visibility Sequence 题解
    题意对于一个长度为\(N\)的序列\(H\),可以通过如下方式构造一个序列\(P\):若存在\(j\in\left[1,i\right)\),使得\(H_j>H_i\),则\(P_i=\max\limits_{j\in\left[1,i\right)\landH_j>H_i}j\),否则\(P_i=-1\)。给定一个长度为\(N\)的序列\(X\),求所有满足如......
  • CF1866M Mighty Rock Tower 题解
    Problem-1866M-CodeforcesMightyRockTower-洛谷先考虑一个\(O(n^2)\)的dp设计状态:\(dp_i\)表示搭\(i\)层的期望转移:\(dp_i=dp_{i-1}\times(1-P_i)+\sum\limits_{j=i}^{n-1}dp_j\timesP_{j+1}^{j-i+1}\times(1-P_{j+1})\),显然是有后效性的,但我们展开......
  • [ARC104E] Random LIS 题解
    题意给定一个长度为\(N\)的序列\(A\),按照下列方式生成一个长度为\(N\)的序列\(X\):\(\foralli\in[1,n]\),\(X_i\)在\([1,A_i]\)中的整数中均匀随机生成。求其最长上升子序列长度的期望,对\(10^9+7\)取模。\(1\leN\le6,1\leA_i\le10^9\)。题解由于\(N\)......
  • CSP-S2023 全场题解
    lock这题就是个模拟吧,赛时被迷惑了以为是什么不可做题,仔细看只有\(10^5\)种状态,那就枚举好了。我们分别从状态串出发,枚举它能达到的答案,加到set取个并集,不过注意给定的状态不能是密码,要减掉。注意不要直接计数器减减,不然如果有相同的算在状态里面的会多减,我考场代码就这么被......
  • NOIP 提高组 题解
    NOIST2023涂色游戏对于每一行每一列记录一个时间戳,对于每个格子颜色即为时间戳较大的颜色。幂次考虑暴力,我们发现\(O(\sqrt[3]{n})\)的复杂度是可以接受的,所以可以枚举\(\sqrt[3]{n}\)内的数然后暴力往上乘,可以用一个unordered_map判重,时间复杂度大概为\(O(\sqrt[3]{n}......
  • 【POJ 1731】Orders 题解(全排列)
    描述商店经理按照标签的字母顺序对各种商品进行了分类。所有标签以同一字母开头的种类都存放在标有该字母的同一仓库(即在同一建筑物内)。在白天,商店经理接收并预订要从商店发货的货物订单。每个订单只需要一种货物。商店经理按照预订的顺序处理请求。你事先知道今天商店经理必须处......
  • flask部署在腾讯云上,但在本地使用网页无法访问——问题解决
    flask部署在腾讯云上,但在本地使用网页无法访问——问题解决1.修改腾讯云防火墙,把对应的port开放:2.修改代码if__name__=='__main__':app.run(host="0.0.0.0",port=5000,debug=True)参考链接:https://zhuanlan.zhihu.com/p/611969276......
  • HCIP Datacom H12-831考题解析
    OSPFv3专题6.关于0SPFv3报文,以下哪个描述是正确的?郑锦程校对整理2023.11.03A.OSPFv3的Hello报文携带了路由器所有接口的IPv6地址B.OSPFv3使用链路本地地址作为发送报文的源地址,报文可以被转发到始发链路范围之外C.OSPFv3使用IPv6组播地址FF02:1和FF02:2发送OSPFv3报文D.可以在OSPFv......
  • 【真题解析】软件工程-重点题目解析(1)
    截止2023年4月本系列是我自己在学习过程中记录的资料;因为内容比较格式比较多样;用markdown靠记录非常浪费时间;再加上对时效性的考虑;就以PPT的形式记录了;本系列因为是自己的理解为主,因此,难免与教材中的内容有误差,主要是从自己的知识角度解释题目的答案,个人感觉是有助于记忆的。如果有......
  • 苏格拉底问答、实践过程截图、遇到问题解决问题截图,代码链接
    #include<signal.h>#include<stdio.h>#include<sys/time.h>intcount=0;structitimervalt;voidtimer_handler(intsig){printf("timer_handler:signal=%dcount=%d\n",sig,++count);if(count>=8){printf("cancel......