我卢本伟没有开挂！

一时失言乱红尘 2022-04-13 06:56 132阅读 0赞

### 题目描述 ###

众所周知，卢本伟没有开挂，如何验证他没有开挂呢？这里我们发现一个算法通过输出d能够证明他有没有开挂  
1：如果 n = 0，结束算法  
2：find the smallest prime divisor dd of nn;  
3：n减去d并且跳转到第一步  
输入  
仅包含一个整数n(2<=n<=10^10)  
输出  
仅输出一个整数,这个算法最后得到的操作的次数  
样例输入  
5  
样例输出  
1

##### 分析： #####

本题看似简单，但是如果将素数打表或者直接判断都会时间超限。通过不断分析样例我们会发现一个偶数，他每次减去的素数都是2， 所减去的次数即是n/2；这是一个偶数的情况，那么一个奇数，我们会发现，他减去他所能整除的最小素数。那么就会变成偶数。所以可以通过这样来判断。然后特殊情况是当n=1 的时候。n=1 那么所减次数也是1次。

#include"stdio.h"
    long long b[10001];
    long long isprime(long long a)
    {
    
        long long i,j,k,t;
        for(i=2;; i++)
        {
            if(a%i==0)
                for(j=2; j<i; j++)
                    if(i%j==0)
                        break;
            if(j==i)
                return j;
        }
    }
    int main()
    {
        long long n,i,d,j;
    
        while(~scanf("%lld",&n))
        {
            d=0;
            if(n%2==0)
            {
                d=n/2;
            }
            else
            {
                if(n==1)
                    d=1;
                else if(n!=1)
                {
                    n=n-isprime(n);
                    d=1+n/2;
                }
    
            }
            printf("%lld\n",d);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

相关 FastJson 我大意了，我没有闪

前言我没有闪正文最近在做项目，在对象判空的时候，根据业务需求，写了个自动判空的方法 isEmpty（）。代码示例：

谁践踏了优雅/ 2022年12月24日 01:50/ 0 赞/ 177 阅读

相关【k8s】volum “istio-token“ 没有挂上

简述在配置k8s的时候就遇到来这个错误，找了很久。 1. 打开 `/etc/kubernetes/manifests/kub-apiserver.yaml` 2.

骑猪看日落/ 2022年11月07日 13:16/ 0 赞/ 86 阅读

相关会Python了不起吗？是的，简直开挂！

最近技术圈掀起了一股 Python “地图” 风潮，所谓“地图” 是指一种学习方式。每个人都想拥有更多的知识。很多同学因为专业所需或是寻求更好的发展，而对 Pytho

矫情吗；*/ 2022年10月08日 09:02/ 0 赞/ 124 阅读

相关 Redis 6.x 了不起吗？是的，简直开挂！

阿里云 Redis 从 2015 年商用以来，一直是全球领先的云KV内存数据库产品，自从正式推出云数据库Redis 6.0版本，包含多项重大功能更新和大幅度的性能提升。相比于社

╰+哭是因爲堅強的太久メ/ 2022年10月04日 15:48/ 0 赞/ 136 阅读

相关我的第一本pdf！

大家好，我是bigsai，第一次将部分文章整理成pdf分享给大家。自己写东西断断续续也不少时间了，也写了不少东西(虽然是偏向小白)，这个其实花费的时间还是比较多的，这次的话

Bertha 。/ 2022年09月09日 09:21/ 0 赞/ 137 阅读

相关我卢本伟没有开挂！

题目描述众所周知，卢本伟没有开挂，如何验证他没有开挂呢？这里我们发现一个算法通过输出d能够证明他有没有开挂 1：如果 n = 0，结束算法 2：find the

一时失言乱红尘/ 2022年04月13日 06:56/ 0 赞/ 133 阅读

相关卢卡斯定理

前言：可以用来计算 $C\_\{n\}^\{m\}\\%p$ 正文：卢卡斯定理卢卡斯定理适用于模数 $p$ 为质数的情况首先我们知道组合数的计算公

小灰灰/ 2021年12月16日 04:36/ 0 赞/ 208 阅读

相关 flink作业多次挂掉，代码逻辑没有问题

由于代码为公司内部资源，不可以泄露，所以不能提供代码和截图。现象：在一次修改线上代码后，能够执行正常业务，但是作业经常频繁挂掉。在日志中没有提示代码逻辑有问题，显示的

太过爱你忘了你带给我的痛/ 2021年10月12日 23:53/ 0 赞/ 376 阅读

相关红米成立独立公司金立前总裁卢伟冰或挂帅PK华为荣耀

![红米成立独立公司金立前总裁卢伟冰或挂帅PK华为荣耀][_PK] 雷帝网乐天 1月3日报道小米集团今日公布2019年的第一个大动作：红米正式改名为Redm

- 日理万妓/ 2021年09月18日 00:14/ 0 赞/ 214 阅读

相关我说我不会算法，阿里把我挂了。

前言工作已经有一段时间了，有的时候会跟同事们打趣：“如果你让我现在去手写一个快速排序，我怕是真的写不出来”。如果不接触一段时间的算法，真的很容易就忘了。不信？你现在

绝地灬酷狼/ 2021年08月27日 17:38/ 0 赞/ 397 阅读