题意
珂朵莉给你一个数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}}。
完结
