题意
珂朵莉给你一个数n(1\leq{n}\leq{10^{10}}),循环执行如下操作,初始时m=0
- 若n=0,则结束循环
- 找到n最小的质因数d
- n-=d
- m++
- 前往步骤1
循环结束时输出m(其实就是操作次数)
题解
很容易发现n为偶数时,操作2找到的d=2,偶数减偶数还是偶数,所以:
更容易地发现当n为质数时,找到的d=n,n-n=0,所以:
剩下的情况就是n是奇合数了,只要循环枚举n以内的奇数,第一个找到的n的约数的数(很容易知道一定是质数)就是d。
设操作2的函数叫findmin()
所以:
注意n最大为10^{10},超过了MAX\_INT,所以要用long\ long
代码
注: 用了一点位运算,详见最后的说明。
因为n是long\ long,常量定义默认是int型,所以最好养成好习惯加一个ll
在常量数字后面
#include<cstdio>
long long n,res; //记得long long
bool isprime(long long x) //借用某大佬O(n/6)的质数判断
{
if(x==1ll) return false;
if(x==2ll||x==3ll) return true;
if(x%6ll!=1ll&&x%6ll!=5ll) return false;
for(register long long i=5ll;i*i<=x;i+=6ll)
if(!(x%i)||!(x%(i+2ll))) return false;
return true;
}
long long findmin(long long x) //findmin函数
{
for(register long long i=3ll;i*i<x;i+=2)
if(!(x%i)) return i;
return 0ll;
}
int main()
{
scanf("%lld",&n);
if(isprime(n)) printf("1\n"); //如果n是质数就输出1
else if(!(n&1)) printf("%lld\n",n>>1ll); //如果n是偶数就输出n/2
else printf("%lld\n",((n-findmin(n))>>1ll)+1ll); //否则就输出(n-findmin(n))/2+1
return 0;
}
说明
关于本篇涉及到的位运算的讲解(其实就一个)
x>>1
表示x/2
,其实x>>i =\frac{x}{2^{i}}。
完结